### Bucket Sorting Algorithm

closed account (SGb4jE8b)
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394`` `````` /* Author: Peter Nwanosike Date: 11/12/2012 This program shows the algorithm for the bucket sorting technique like order sorting algorithm. Although, this program is not as efficient as the quicksort algorithm that uses a fewer comparison and have a Nlog2(N) bigO efficiency and speed. It however shows how the bucketsort algorithm works. Please, remember to contact me at dexter4life@gmail.com or search for me on the cplusplus.com forum using dexter as the search key; if not okay, go to facebook and search for "peter Nwanosike" I will love to reply to any of the questions ask. Enjoy the Code. Coding is fun!!!!!!!!!!! */ #include #include using namespace std; void __fastcall printArray( int [], int ); int getPosition( int n, int count ) { if ( count == 0 ) return n%10; else return getPosition( n/10, count-1 ); } inline bool isSorted( int array[], int size ) { for ( int i = 1; i < size; i++ ) { if ( array[i-1] > array[i] ) return false; else ; //do nothing } return true; } inline void __fastcall InitializeBucket( int *b[10], int row, int col ) { for ( int i = 0; i < row; i++ ) for ( int j = 0; j < col; j++ ) b[i][j] = -1; } void __fastcall bucketSort( int array[], int size ) { const int row = 10;//0-9 bool flag = false; int iCount = 0, position = 0; //int bucket[row][col] is same as below (dynamic memory allocation 'dma'); int *bucket[row]; for ( int i = 0; i < row; i++ ) bucket[i] = new (nothrow) int[size-1]; //nothrow set bucket to null when no sufficient memory. //initialize bucket to -1, so that gathering will be easy InitializeBucket(bucket, row, size ); //initialize bucket to -1 while( !flag ) // loop until sorted is true { for ( int i = 0; i < size; i++ ) { if ( isSorted( array, size ) ) flag = true; //set flag to true for loop termination bucket[getPosition(array[i], position)][i] = array[i]; // distribution of values according to places values } for ( int j = 0; j < row; j++ ) //for the gathering of values { for ( int k = 0; k < size; k++ ) if ( bucket[j][k]!=-1 ){ array[iCount] = bucket[j][k]; //gather for every pass ++iCount; } } InitializeBucket(bucket, row, size ); //reinitialize bucket for further use ++position; //increment for place value iCount = 0; //set iCount to 0, so that will start from first index } delete [] bucket; } void __fastcall printArray( int array[], int size ) { for ( int index = 0; index < size; index++ ) cout << array[ index ] << ' '; cout << endl; } int main() { const int aSize = 30; int myArray[aSize]; //unsorted list srand((unsigned)time(NULL)); //seed rand function for ( int index = 0; index < aSize; index++ ) myArray[index] = rand()%20; //generate rand value for sorting cout << "Before the sorting: \n"; printArray( myArray, aSize ); bucketSort( myArray, aSize ); //bucket sorting algorithm cout << "After the sorting: \n"; printArray( myArray, aSize ); system("pause"); return 0; }``````
Are you asking why does this program crash when executed as written (or why does it leak so much memory if it chances not to crash) or how to complete its translation from C to C++?
Last edited on
closed account (SGb4jE8b)
why does it leak so much memory?
Because none of the arrays allocated in this loop is ever decallocated
`for ( int i = 0; i < row; i++ ) bucket[i] = new (nothrow) int[size-1];`
closed account (SGb4jE8b)
I thought using the deallocating statement this ` delete [] bucket ` covers every of the allocated memory.
Topic archived. No new replies allowed.