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;
}
|
