Article 98 - Bucket Sort Implementation

This article describes an implementation of the Bucket Sort Algorithm.

For information about the Bucket Sort Algorithm, see Article 35 - Programming Sorting Algorithms.

Implementation

In this implementation, we use the Node structure from the Link List Article, see Article 83 - Data Structure - How to Implement Linked List in C.

To make the implementation challenging, we will swap nodes instead of swapping content.

This algorithm makes use of an algorithm that picks out the digit at a particular place value of an integer, see Article 94 - How to Get a Specific Digit of an Integer?

Bucket Sort implementation.

int bucketSortHelper( Node ** list, unsigned int place ){
    Node * buckets[10];
    Node * listPointer;
    Node * listPointerNext;
    int digit;    

    if( !list ){
        return -1;
    }

    if( !*list ){
        return 0;
    }

    if( place == 0 ){
        return 0;
    }

    memset( buckets, 0, sizeof( Node ) * 10 );

    //move each node to the bucket based on digit at the specific place
    for( listPointer = *list; listPointer; ){
        digit = getDigitAt( listPointer->content, place );

        listPointerNext = listPointer->next;

        if( addNode( &buckets[digit], listPointer ) ){
            return -2;
        }

        listPointer = listPointerNext;
    }

    *list = 0;

    //recursively sort the next placevalue and merge buckets
    for( digit = 0; digit < 10; digit++ ){
        if( buckets[digit] ){
            if( bucketSortHelper( &buckets[digit], place - 1 ) ){
                return -3;
            }

            if( !*list ){
                listPointer = buckets[digit];
                *list = listPointer;
            }
            else{
                listPointer->next = buckets[digit];
            }

            //bring listPointer to the end of the current sorted list
            for( ; listPointer; listPointer = listPointer->next){

            }
        }
    }

    return 0;
}

int bucketSort( Node ** list ){
    //assume maximum of 10 digits
    return bucketSort( list, 10 );
}

Comments (1)

Posted by anonymous - Carolina27Rivera at Friday, March 1, 2013 4:08 AM

I strictly recommend not to wait until you earn enough amount of money to buy different goods! You should just get the <a href="http://goodfinance-blog.com/topics/home-loans">home loans</a> or student loan and feel fine

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.