기수 정렬 < 연결 리스트 판 > ( Radix Sort < Linked List Version > )

* Radix Sort ver. Linked List


main.cpp

#include "Radix_Sort.h"

int main()
{
 // sample
 Radix_Sort("input.txt","output.txt");

 // example
 Radix_Sort("example1.txt","result1.txt");

 // example
 Radix_Sort("example2.txt","result2.txt");

 return 0;

}

Node.h

#ifndef NODE_H
#define NODE_H

class Node
{
public:
 int data;
 Node* next;

 Node() : next(NULL) {}
};

#endif

Radix_Sort.h

#ifndef RADIX_SORT_H
#define RADIX_SORT_H

#include <iostream>
#include <fstream>
#include "Node.h"
using namespace std;

void Radix_Sort(char* input_file, char* output_file)
{
 fstream Input, Output;
 int N,D;
 char* buf;
 Node* t;
 Node* head = NULL;
 Node* dummy[10];

 // input file read..
 Input.open(input_file,ios::in);
 Input >> N;
 Input >> D;

 buf = new char[D+1];

 // make list
 while(!Input.eof())
 { 
  if(!head) 
  {
   t = new Node();
   head = t;
   Input >> t->data;
  }
  else
  {
   t->next = new Node();
   Input >> t->next->data;
   t = t->next;
  }
 }

 // radix sort
 Output.open(output_file,ios::out);
 for(int k=1,s=1,i;k<=D;k++)
 {
  _itoa_s(k,buf,D+1,10);
  Output << "Pass " << buf << endl;

  //dummy pointer init
  for(i=0;i<10;i++)
  {
   dummy[i] = NULL;
  }

  // bin sort
  for(Node* p = head,*d,*q;p;)
  {
   i = static_cast<int>(p->data/s)%10;

   // link to dummy pointer's tail
   if(!dummy[i])
   {
    dummy[i] = p;
    q = p->next;
    p->next = NULL;
   }
   else
   {
    d = dummy[i];
    while(d->next)
    {
     d = d->next;
    }
    d->next = p;
    q = p->next;
    p->next = NULL;
   }

   p = q;
  }

 
  // print pass
  for(i=0;i<10;i++)
  {
   t = dummy[i];

   Output << "[" << i << "] "; 

   while(t)
   {
    _itoa_s(t->data,buf,D+1,10);
    Output << buf;
    if(t->next)
     Output << "->";
    t=t->next;
   }

   Output << endl;
  }
  Output << endl;

  _itoa_s(k,buf,D+1,10);
  Output << "Result of Pass " << buf << endl; 


  // make result
  head=NULL;
  for(i=0;i<10;i++)
  {
   if(!head)
   {
    head = dummy[i];
   }
   else
   {
    t = head;
    while(t->next)
    {
     t = t->next;
    }
    t->next = dummy[i];
   }
  }


  //print result
  t=head;
  while(t)
  {
   Output << t->data << " ";
   t=t->next;
  }
  Output << endl << endl;


  s = s * 10;
 }
 Output.close();

 // test
 t=head;
 while(t)
 {
  cout << t->data << " ";
  t=t->next;
 }
 cout << endl;
}


#endif