C++

Forum

 
Sorting problem

sharris (21)
Hello everyone!

I'm far from understanding all I do with C++ so please forgive my foolish mistakes. I'm sure it's something simple but I don't know what I did wrong. Could someone show me how to correct the bucket sort function at the bottom of the page. Everything else works perfectly. I think that my math is incorrect or something is out of place. The program will only output ½ of the number (5 out of 10) and I can't tell if it's even on its way to sorting properly.

Thanks in advance.

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
 
#include <iostream> 
#include <cstdlib>
#include <ctime>

using namespace std;

void BucketSort(int a[], int size);

int main()
{
    const int size = 10;
    int data[size];
    srand(119523);
   
    for (int i = 0; i < size; i++) {
        data[i] = rand()% 100;
    }
// .......................................
    cout << "Original  order  :";
    for (int i = 0; i < size; i++) {
        cout << "  " << data[i];   }
    cout << endl;
    cout << endl;
// .......................................
    cout << "After Bucket sort:";
    BucketSort( data, size );
    cout << endl;
    cout << endl;

system("pause");
}

void BucketSort(int a[], int size)
{
    int *ptr[10];
    int pcount[10];
    for (int i = 0; i < size; i++) { 
        ptr[i] = new int[size];
    }
    
      for (int div = 1; div <= size / 2; ++div) {

          cout << "  " << a[div];   }  }

kbw (9488)
The algorithm description and pseudo code are here: http://en.wikipedia.org/wiki/Bucket_sort

So far you've create an array of int filled with random values to be sorted. That's good.

You've printed the array, so you can see the unsorted values. That's good.

You've called BucketSort to sort your data. That's good.

You don't print the sorted array after calling BucketSort. That's bad. It's just the same code that prints the unsorted array.

BucketSort doesn't sort. That's bad. You need to understand the algorithm and implement it. There's plenty of help in the Wikipedia link. You need to decide how many buckets you're going to use apriori, you don't create a bucket for each element. You probably need just 2 or 3 for a 10 element list.
sharris (21)
I got tons of Wiki and doc's from C++ to QUANTUM about the subject and http://en.wikipedia.org/wiki/Bucket_sort is the most recommended read. I guest it's time the read that Wiki and thanks for something about my progress. Sometime I think I missed the mark. It feels good to know that one has line the code up properly for it propose. WoW!

I read a lot, but very few doc's to it fullest because I learn mostly code buy trial and error, cut and paste. Now that I got a real clue ... I can't wait to hit those doc's!

Thanks kbw
sharris (21)
You really motivated me kbw. Thank You


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
 
//        http://en.literateprograms.org/Bucket_sort_(Java)
//        BucketSort Array

#include <vector>
#include <iostream> 
#include <cstdlib>
#include <ctime>

using namespace std;
 void bucketSorter(int DATA[],int length, int COUNT);

 
int main()
{
	int DATA[]    =    {90, 90, 90, 80, 70, 60, 50, 40, 30, 30};
	int element   =    sizeof(DATA)/sizeof(int);
	int COUNT     =    DATA[0];

// .......................................
    cout << "Original  order  :";
    for (int i = 0; i < element; i++) {
        cout << "  " << DATA[i];   }
    cout << endl;
    cout << endl;
// .......................................
    cout << "After Bucket sort:";
 	bucketSorter(DATA, element, COUNT);
	getchar();
}
//  ..............................................
//  ..............................................
void bucketSorter(int DATA[],int length, int COUNT)
     {
     int* bSort = new int[COUNT];
     int SIZE = length;
 
     for( int B  = 0  ;  B <= COUNT ;  ++B )   {
          bSort[B] = 0; }


     for(int A = 0 ; A < SIZE ; ++A)          {
          ++bSort[DATA[A]];  }	



     for( int A = 0, B = 0  ;  B <= COUNT  ; ++B )   {
          for(int C = bSort[B]  ;  C > 0  ;  --C )   {
		                      DATA[A++] = B;  } }  //  it matters here A++ not ++A



     for( int A = 0  ;  A < SIZE  ;  ++A )
	 {
         cout << "  " << DATA[A];
     }	
         cout << endl;
}

kbw (9488)
The function bucketSorter shouldn't print anything, it should just perform the sort. You can add diagnostic prints while developing, but in the end it shouldn't print anything.

Back to bucketSorted, I take it COUNT is the number of buckets to use. If that's the case, why are you using 90 buckets? We'll put that aside for now.

A bucket is a data structure that can hold zero or more items, so it's an array of numbers that can grow. So for each bucket, you'll need to keep track of the array and the number of elements in the array.

How big must the array be? Well, we know it doesn't need to be larger than the total number of elements you want to sort, just encase all the numbers end up in one bucket.

So when you enter BucketSorter, you can allocate COUNT number of arrays of size length and allocate COUNT number of ints to record the number of elements in each bucket. The standard vector does this nicely, but as this is most probably homework you may not be allowed to use it.

Next, you have to decide on the value range of each bucket.

The you loop thru your numbers and add them to the relevant bucket.

Then you sort each bucket.

Then you take the numbers out of each bucket and replace the numbers in your array.
sharris (21)
kbw, I' done fairly well using FASM since 2003 and MASM since 1999 but have done nothing with it for over 4 years. Coding is my hobby and I think C++ is harder to learn but I will catch on. Anyway, where can I find this vector Bucket example?

btw, what kind of sorting am I doing with this algorithm. Is it only counting.
Last edited on
kbw (9488)
Have you read the the Wikipedia Bucket Sort algorithm link I posted earlier? It's all explained there.
jumper007 (435)
... im really confuse 
1
2
3
 
for( int A = 0, B = 0  ;  B <= COUNT  ; ++B )   {
          for(int C = bSort[B]  ;  C > 0  ;  --C )   {
		                      DATA[A++] = B;  } }  //  it matters here A++ not ++A

why not ++A ? I know what ++A and A++ means but i cant get it why is ++A not ok ?
Last edited on
sharris (21)
I read a link here about a month ago and a guy said it don't matter if you ++i or i++, and he made it clear that ++i makes cleaner code so I been using that every since and than I notices a few days ago while preparing this algorithms to my coding style the program would not compile when I did it like this DATA[++A] = B; } } My guest is the = equate operator that demand it to of standard way "A++" i++. You learn a lot of things when you tinker around. I do that with all of my spare time sometimes.

Btw: it works on my devcpp.exe even when I get the file from here. Maybe someone don't want me to seen it. The algorithms is beautiful but it seems I was barking up the wrong tree as a bucketSORT. I was told this was a counting sort... Now I'm confussed too.

I'll check it out and zip it next time. Give me a day.





Have you read the the Wikipedia Bucket Sort algorithm link I posted earlier? It's all explained there.


kbw, yes I did but only had pesudo-code that I did not understand. Four hours of trying went down the drain. Check out the complete list below... No C++ but a little pseudo-code.


I can write some pseudo-code but I can't understand all. I am a trial and error person. I got to see the code too. Than I checked out a full working JAVA source on wiki that gave me the additional clue.

Wikipedia:
Bucket sort (PHP) (1840 bytes)
Bucket sort (Java) (2054 bytes)
Bucket sort (C) (2023 bytes)
Bucket sort (Python) (1752 bytes)
But no C++

Today I found these on my machine downloaded months. I been trying for weeks and searching for a clues with all my spare time and had it along, maybe. This sounds like true bucketSort for C++. Is one or both of these the true working buckSort algorithm for C++? Also, is what I presented in the code above is DEFINITELY is not a true buckSORT code?. I like C++ for the Vector, MAP and it, for months. I beleive these are the only type questions I had from day-1 posted here. You got to have something to love or go back to simple ASM. C++ is not that bad.

1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
void bucketSort(int *inArr, int arrSize, int variance){
  int *bucket = (int*)malloc(sizeof(int) * variance);  
  // Initialize all bucket nodes to have a count of 0
  memset(bucket, 0, sizeof(int) * variance);
  // Throw the count of each node into the bucket
  for (int i = 0; i < arrSize; i++){
    bucket[inArr[i]]++;
  }
  // We'll fill the new array with whatever is in the bucket
  int newArrayPosition = 0;
  for (int x = 0; x < variance; x++){
    for (int j = 0; j < bucket[x]; j++){
      inArr[j + newArrayPosition] = x;  
    }
    newArrayPosition += bucket[x];
  }
 
  free(bucket);
}



2)
1
2
3
4
5
6
7
8
9
10
11
12
 
void BucketSort (unsigned int a [], unsigned int n)
{
    int buckets [m];

    for (unsigned int j = 0; j < m; ++j)
	buckets [j] = 0;
    for (unsigned int i = 0; i < n; ++i)
	++buckets [a [i]];
    for (unsigned int i = 0, j = 0; j < m; ++j)
	for (unsigned int k = buckets [j]; k > 0; --k)
	    a [i++] = j;
}


Last edited on
sharris (21)
Last edited on
Topic archived. No new replies allowed.