기수 정렬 < 연결 리스트 판 > ( Radix Sort < Linked List Version > )
Radix Sort ver. Linked List
Rule
Source Code
main.cpp
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
cpp
#ifndef NODE_H
#define NODE_H
class Node
{
public:
int data;
Node* next;
Node() : next(NULL) {}
};
#endif
Radix_Sort.h
cpp
#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