1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
|
/*
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 <iostream>
#include <iomanip>
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;
}
|