Radix sort
From Algorithm wiki
 Related content:
|
Contents |
[edit] PSEUDOCODE =
Radix Sort in pseudo code
'''Radix_Sort(A, digit)'''\n
1. for i <- 1 to digit \n
2. '''do''' use a stable sort array '''a''' on digit i\n
'''PROGRAM CODE IN C-'''
#include < stdio.h>
#include < conio.h>
#include < stdlib.h>
void radix(int a[],int n,int m)
{
typedef struct node
{
int data;
struct node * next;
}NODE;
NODE * ptr,*start,*prev;
NODE *front[10], *rear[10];
int k=1,i,j,y,p;;
/*creating initial linked list*/
start=NULL;
for(i=0;i< n;++i)
{
ptr=(NODE *)malloc(sizeof(NODE));
ptr->data=a[i];
ptr->next=NULL;
if(start==NULL)
start=ptr;
else
prev->next=ptr;
prev=ptr;
}
/*radix sort*/
for(i=1;i< =m;++i)
{
for(j=0;j< 10;++j)
front[j]=NULL;
/*placing elements into queues*/
ptr=start;
while(ptr!=NULL)
{y=ptr->data/k %10;/*y is the digit*/
if(front[y]==NULL)
{
front[y]=ptr;
rear[y]=ptr;
}
else
{
rear[y]->next=ptr;
rear[y]=ptr;
}
ptr=ptr->next;
}
start=NULL;
for(j=0;j< 10;++j)
if(front[j]!=NULL)
{
if(start==NULL)
start=front[j];
else rear[p]->next=front[j];
p=j;
}
rear[p]->next=NULL;
k=k*10;
}
/*copying back to array*/
ptr=start;
for(i=0;i< n;++i,ptr=ptr->next)
a[i]=ptr->data;
}
void main()
{
int a[100],n,i,m;
char temp;
do
{
clrscr();
printf("===========================RADIX SORT===========================================\n");
printf("ENTER NUMBER OF NUMBERS AND NUMBER OF DIGITS\n");
scanf("%d%d",&n,&m);
printf("ENTER ELEMENTS\n");
for(i=0;i< n;++i)
scanf("%d",&a[i]);
radix(a,n,m);
printf("SORTED LIST\n");
for(i=0;i< n;++i)
printf("%d ",a[i]);
printf("\nDO YOU wish to continue?[y/n]\n");
scanf("%c",&temp);
}while(temp=='y'|| temp=='Y');
printf("\n---------------------------------------------------------------------------------\n");
getch();
}
#include < stdio.h>
#include < conio.h>
#include < stdlib.h>
void radix(int a[],int n,int m)
{
typedef struct node
{
int data;
struct node * next;
}NODE;
NODE * ptr,*start,*prev;
NODE *front[10], *rear[10];
int k=1,i,j,y,p;;
/*creating initial linked list*/
start=NULL;
for(i=0;i< n;++i)
{
ptr=(NODE *)malloc(sizeof(NODE));
ptr->data=a[i];
ptr->next=NULL;
if(start==NULL)
start=ptr;
else
prev->next=ptr;
prev=ptr;
}
/*radix sort*/
for(i=1;i< =m;++i)
{
for(j=0;j< 10;++j)
front[j]=NULL;
/*placing elements into queues*/
ptr=start;
while(ptr!=NULL)
{y=ptr->data/k %10;/*y is the digit*/
if(front[y]==NULL)
{
front[y]=ptr;
rear[y]=ptr;
}
else
{
rear[y]->next=ptr;
rear[y]=ptr;
}
ptr=ptr->next;
}
start=NULL;
for(j=0;j< 10;++j)
if(front[j]!=NULL)
{
if(start==NULL)
start=front[j];
else rear[p]->next=front[j];
p=j;
}
rear[p]->next=NULL;
k=k*10;
}
/*copying back to array*/
ptr=start;
for(i=0;i< n;++i,ptr=ptr->next)
a[i]=ptr->data;
}
void main()
{
int a[100],n,i,m;
char temp;
do
{
clrscr();
printf("===========================RADIX SORT===========================================\n");
printf("ENTER NUMBER OF NUMBERS AND NUMBER OF DIGITS\n");
scanf("%d%d",&n,&m);
printf("ENTER ELEMENTS\n");
for(i=0;i< n;++i)
scanf("%d",&a[i]);
radix(a,n,m);
printf("SORTED LIST\n");
for(i=0;i< n;++i)
printf("%d ",a[i]);
printf("\nDO YOU wish to continue?[y/n]\n");
scanf("%c",&temp);
}while(temp=='y'|| temp=='Y');
printf("\n---------------------------------------------------------------------------------\n");
getch();
}
[edit] PHP Code
/**
* ce7077@163.com
*/
class RadixSort
{
protected $ary = array();
protected $len = 0;
protected $d = 3;
protected $order = array();
protected $tmp = array();
function __construct( $ary= array(), $d=10 )
{
if(!empty($ary))
{
$this->ary = $ary;
}
$this->len = count($this->ary);
$this->d = $d;
for($i=0;$i<$this->len;$i++)
{
$this->order[$i] = 0;
for($z=0;$z<$this->len;$z++)
{
$this->tmp[$i][$z] = 0;
}
}
$this->doSort();
}
public function getRs()
{
Return $this->ary;
}
private function doSort()
{
$n=1;
for($m=1;$m<=$this->d;$m++)
{
for($i=0; $i<$this->len; $i++)
{
$lsd = floor($this->ary[$i]/$n)%10;
$this->tmp[$lsd][$this->order[$lsd]++] = $this->ary[$i];
}
$k=0;
for($s=0; $s<10; $s++)
{
if($this->order[$s] != 0 )
{
for($j=0; $j<$this->order[$s]; $j++)
{
$this->ary[$k++] = $this->tmp[$s][$j];
}
}
$this->order[$s] = 0;
}
$n *=10;
}
}
}
echo('<pre>');
$rs =new RadixSort(array(73,22,93,43,55,14,28,65,39,81,33,100),3);
print_r($rs->getRs());
[edit] C# Code
[edit] Java Code
import java.util.*;
public class RadixSort
{
String[] input;
int maxLength;
public RadixSort(String[] sa)
{
input = sa;
maxLength = input[0].length();
for (int i = 1; i < input.length; ++i){
if (input[i].length() > maxLength){
maxLength = input[i].length();
}
}
}
public String[] sort()
{
for (int i = maxLength -1; i > -1; --i){ //begin compare from the last char
//Arrays.sort take O( n lg n) but radix should take O(kn)
Arrays.sort(input, new RadixComparator(i));
}
return input;
}
// give two or more strings as command line args
// ex. java RadixSort vouch wacky lover love banana ananas
public static void main(String[] args)
{
String Str[]={"9","5","2","8"};
RadixSort rs = new RadixSort(Str);
String[] result = rs.sort();
for (int i = 0; i < result.length; ++i)
{
System.out.println(result[i]);
}
}
}
class RadixComparator implements Comparator<String>
{
int columnNum; //start from 0
public RadixComparator(int col)
{
columnNum = col;
}
public int compare(String s1, String s2)
{
int l1 = s1.length();
int l2 = s2.length();
if (l1 < (columnNum + 1)){ //s1 too short
if (l2 < (columnNum + 1)){ //both too short
return 0;
}
else{
return -1;
}
}
else if (l2 < (columnNum + 1)){ //s2 too short
return 1;
}
else{
char c1 = s1.charAt(columnNum);
char c2 = s2.charAt(columnNum);
return c1 - c2;
}
}
}
[edit] VB Code
This section needs your Code!
[edit] Perl Code
This section needs your Code!
[edit] Prolog Code
This section needs your Code!
[edit] Python Code
This section needs your Code!
[edit] Ruby Code
This section needs your Code!
