Bucket Sorting Algorithm

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;
}
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
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];
I thought using the deallocating statement this delete [] bucket covers every of the allocated memory.
Topic archived. No new replies allowed.