ในเรื่องของ Radix Sort การจัดเรียงแบบ Radix นั้น เราจะเล่นกันที่หลักสิบ, หลักร้อย หลักพัน ไปเรื่อยๆ ... นี่คือการเรียงแบบ Radix Sort ซึ่งในการจัดเรียงแบบนี้นั้น เราจะเริ่มดูที่หลักหน่วยก่อน จากนั้นไปหลักสิบ, ร้อย, พัน... ดังเช่น เรามีตัวเลขอยู่ดังนี้

38,28,18,58,64,44,74,87

ถ้าเราจะเรียงตัวเลขข้างบนด้วยเทคนิค Radix นั้น เราจะจัดเรียงลําดับเลขในชุดนี้โดยดูหลักหน่วยก่อน เรียงมันจากน้อยไปมาก ก็จะได้ดังนี้

64 44 74 87 38 28 18 58

เห็นมั้ยครับว่า หลักหน่วยได้เรียงแล้ว ต่อไปเราก็จับเรียงในหลักสิบ หลักสิบมีเท่าไหร่ ก็เรียงจากน้อยไปมาก มันก็จะสลับกันได้ดังนี้

18 28 38 44 58 64 74 87

นี่ก็คือวิธีการจัดเรียงแบบ Radix ซึ่งเทคนิคนี้ได้นําเสนอเอาไว้ในหนังสือ Data Structure : implement through C/C++ แต่คราวนี้ จะมา implement โดยใช้อาเรย์แทน คือ ปกติแล้วเราจะใช้อาเรย์ในการจัดการก็ได้ มันก็ง่ายหน่อย แต่ก็จะต้องออกแบบคลาสนะครับ คลาสนี้ที่จะนําเสนอกันก็คือคลาส array จะคล้ายๆ กับคลาส linkedlist ครับ แต่อันนี้จะเล่นเป็นอาเรย์แทน ได้ผลเหมือนกันครับผม

เรามาดูคลาสกันนครับ พร้อมกับตัวอย่างการ Sort แบบ Radix ครับผม

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

class array
{
#define MAX 500

int number[MAX];
int current;

public:
int nav;
array()
{
nav=0;
current=0;
for (int i=0;i<MAX;i++) number[i]=0;
}
~array()
{
removeall();
}

void start()
{
nav=0;
}
bool notend()
{
if (nav!=current)
return true;
else
return false;
}
void next()
{
nav++;
}
int getnum()
{
return number[nav];
}

void addnum(int what)
{
number[current]=what;
current++;
}

void removeall()
{
for (int i=0;i<MAX;i++) number[i]=0;
current=0;
}
};

#define MAX 10

void main()
{
array radix[10];

int i;
int number[MAX];

// random numbers into an array
srand(unsigned(time(NULL)));
for (i=0;i<MAX;i++)
{
number[i]=rand()%50+10;
}

for (i=0;i<MAX;i++)
{
int which=number[i]%10;
radix[which].addnum( number[i] );
printf("add %d to [%d]\n",number[i],which);
}
for (i=0;i<10;i++)
{
printf("Radix[%d]=",i);
for (radix[i].start();radix[i].notend();radix[i].next())
{
static int count=0;
number[count]=radix[i].getnum();
printf("%d ",number[count]);
count++;
}
printf("\n");
radix[i].removeall();
}
printf("=== PASS 1 ===\n");
for (i=0;i<MAX;i++)
{
printf("%d ",number[i]);
}
printf("\n");

for (i=0;i<MAX;i++)
{
int which=number[i]/10;
radix[which].addnum( number[i] );
printf("add %d to [%d]\n",number[i],which);
}
for (i=0;i<10;i++)
{
printf("Radix[%d]=",i);
for (radix[i].start();radix[i].notend();radix[i].next())
{
static int count=0;
number[count]=radix[i].getnum();
printf("%d ",number[count]);
count++;
}
printf("\n");
radix[i].removeall();
}
printf("=== PASS 2 ===\n");

for (i=0;i<MAX;i++)
{
printf("%d ",number[i]);
}
printf("\n");
}

ผลการรันโปรแกรมจะได้ดังนี้

add 33 to [3]
add 26 to [6]
add 26 to [6]
add 22 to [2]
add 27 to [7]
add 47 to [7]
add 59 to [9]
add 56 to [6]
add 18 to [8]
add 17 to [7]
Radix[0]=
Radix[1]=
Radix[2]=22
Radix[3]=33
Radix[4]=
Radix[5]=
Radix[6]=26 26 56
Radix[7]=27 47 17
Radix[8]=18
Radix[9]=59
=== PASS 1 ===

22 33 26 26 56 27 47 17 18 59

add 22 to [2]
add 33 to [3]
add 26 to [2]
add 26 to [2]
add 56 to [5]
add 27 to [2]
add 47 to [4]
add 17 to [1]
add 18 to [1]
add 59 to [5]
Radix[0]=
Radix[1]=17 18
Radix[2]=22 26 26 27
Radix[3]=33
Radix[4]=47
Radix[5]=56 59
Radix[6]=
Radix[7]=
Radix[8]=
Radix[9]=
=== PASS 2 ===

17 18 22 26 26 27 33 47 56 59