Tuesday, May 17, 2011

Bucket Sort

A bucket sort begins with single subscripted array of positive integers to be sorted and a double subscripted array of integers with rows subscripted from 0 to 9 and columns subscripted from 0 to n-1 where n is the number of values in the array to be sorted.
Algorithm
1. Loop through the single subscripted array and place each of its values in a row of the bucket array based on its ones dight.
2.loop through bucket array. copy each element and past it in data array.
3.Repeat the process for each subsequent positions (tens, hundreds,thousands)
Note:
double subscripted array (bucket ) is 10 times larger than data array. which consume a considerable amount of memory. but its performance is high compared to bubble sort.
##############################################################
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define SIZE 20
#define MAXLENGTH  3        //MAXLENGTH means the number of numbers in a value
//eg. max value in data 9999 then  MAXLENGTH 4
void printArray(int data[]){
int i;
int j;
printf("\n\n");
for(i=0;i<SIZE;i++){
printf("%d \n",data[i]);
}
}
int main(int argc, char** argv) {
int data[SIZE];
int tmpArray[SIZE][10];
int tmpData[10]={0};
//Array initialization
srand(time(NULL));
int i;
for(i=0;i<SIZE;i++){
data[i]=rand()%((int)pow(10,MAXLENGTH));
printf("%d \n",data[i]);
}
//sorting
int power;
for(power=10;power<=(int)pow(10,MAXLENGTH);power*=10){
int j;
for(j=0;j<SIZE;j++){
int bal=data[j]%power;
bal=(int)(((10*bal)/power));
tmpArray[tmpData[bal]][bal]=data[j];
tmpData[bal]++;
}
int l;
for(j=0,l=0;j<10;j++){
int k;
for(k=0;k<tmpData[j];k++,l++){
data[l]=tmpArray[k][j];
}
tmpData[j]=0;
}
}
printArray(data);
return (EXIT_SUCCESS);
}

No comments:

Post a Comment