OSDev.org

Code: Select all

struct Node {
    char  *Data;
    struct Node *Next;
};


struct Node * BucketSort(struct Node *Array){
// Time Complexity: Best Case : Theta N
//               Average Case : Theta N
//                 Worst Case : Theta N*N (ie Insertion Sort)
    #define size 26 // a-z
    struct Node **buckets, *sortedList=NULL;
    int i,k;

	buckets=(struct Node **)malloc(sizeof(struct Node *) * size);

	for(i=0;i<size;++i){ // Init Buckets
        buckets[i]=NULL;
    }

	///////// Drop Items into Buckets ///////////////
	struct Node *p = Array ;
    while(p){
        int pos;
        pos = p->Data[0]-'a' ; // <----------
        buckets[ pos ] = creatNode( p->Data , buckets[pos] );
        p=p->Next;
    }

	//////// Sort Buckets using Insertion Sort /////////////
	for(i=0;i<size;++i){
	    if(buckets[i])
            buckets[i]=InsertionSort(buckets[i]);
    }

	///// concatenate the buckets ////////
    for(i=0;i<size;++i){
        struct Node *currentBucket = buckets[i] ;
	    while( currentBucket ){
            sortedList = creatNode( currentBucket->Data , sortedList);
            currentBucket = currentBucket->Next;
	    }
    }


	//Release All Memory Allocted
	for(i=0;i<size;++i){
             nodeFree( buckets[i] );
        }
        free(buckets);


    return sortedList ;
}

Code: Select all

        pos = p->Data[0]-'a' ; // <----------