Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 03-04-2003
Trauts
All right, I've run out of time to work on this, so can someone please figure out why it isn't working right?

Code:

```// RADIXSORT.CPP #include <math.h> #include "apmatrix.h" #include "apvector.h" int const MAX_LIST_SIZE = 100; // Function: digit // Computes the kth digit in number // // Inputs: integers number and k // Outputs: the kth digit in number int digit(int number, int k) {         return (number/int(pow(10,k-1))) % int(pow(10,k-1)); } // Function: initializeCounters // Initializes all bin counters to zero void initializeCounters(apvector<int> &binCounters) {         for (int i = 0; i < binCounters.length(); i++)                 binCounters[i] = 0; } // Function: addToBin // Insert number in bin structure, as indicated by place // // Inputs: a bin structure bins, a vector of bin counters, //                  a number, and a place // Outputs: bin structure bins and its vector of counters //                        have been altered to reflect addition of number //                        in bin eindexed by place template<class element> void addToBin(apmatrix<element> &bins,                           apvector<int> &binCounters, int number, int place) {         bins[place][binCounters[place]] = number; } // Function: collectBins // Append numbers in bins to list // // Inputs: list, a bin structure, and a vector of the counters for the //                        bin structure // Outputs: a list template<class element> void collectBins(apvector<element> &list, apmatrix<element> &bins,                                 apvector<int> &binCounters) {         //put everything back in one list         //matrix[row][column];         int row = 0;         int col = 0;         for (int i=0; i<list.length(); i++)         {                 //if (bins[row][col] < binCounters[row])                 //if (col < binCounters[row])                 if (binCounters[row] > 0/* && col < binCounters[row]*/)                 {                         list[i] = bins[row][col];                         if (col < bins[row].length())                                 col++;                 }                 else if (col == bins.numcols())                 {                         col = 0;                         //cout << row << " " << col << endl;                         if (row+1 < bins.numrows())                                 row++;                 }         } } // Function: radixSort // Sorts numbers in list into ascending order // // Inputs: list and its length // Outputs: the list with numbers sorted in ascending order template<class element> void radixSort(apvector<element> &list, int n) {         int j, k;         apmatrix<element> bins(10,MAX_LIST_SIZE);         apvector<int> binCounters(10);         initializeCounters(binCounters);         // For k loop controls digit used to classify data.         for (k = 1; k <= 4; k++)         {                 // For j loop iterates through all numbers, putting them into                 // bin determined by kth digit.                 for (j = 0; j < n; j++)                         addToBin (bins, binCounters, list[j], digit(list[j], k));                 collectBins (list, bins, binCounters);                 initializeCounters(binCounters);         } }```
• 03-04-2003
Codeplug
First off, are you sure apmatrix and apvector are implemented correctly?
Looking over the posted code now....

gg
• 03-04-2003
PJYelton
I think you need to add:
Code:

`++binCounters[place];`
after
Code:

`bins[place][binCounters[place]] = number;`
Otherwise you will keep writing over the zero spot in your bins.
• 03-04-2003
Codeplug
Your digit function doesn't work; digit(1234,1) should return 4 right? If so, you can try this (non-elegant) implementation in its place until you work out a math based solution - or use this as is:

Code:

```int digit(int number, int k) {     static char str[25];     sprintf(str,"%d",number);     int pos = strlen(str) - k; //k should not be 0     if (pos >= 0)         return str[pos] - '0';     return 0; }```
gg
• 03-04-2003
PJYelton
The digit function is close, just change it to:
Code:

`return (number/int(pow(10,k-1))) % 10;`
and it should work.
• 03-04-2003
Trauts
Quote:

Originally posted by PJYelton
The digit function is close, just change it to:
Code:

`return (number/int(pow(10,k-1))) % 10;`
and it should work.

Work it out on paper:

If you have 1234:

number/int(pow(10,k-1))) % int(pow(10,k-1));

so:

(1234/10^(k-1)) % 10^(k-1)

if you want the 3... you use 2 as k

if you divide 1234 by 10 (10^1), its an int so it ends up as 123.

123 modulus 10 is the remainder of 123/10... thats 3

[EDIT]All right... I was wrong. Your way cuts off the leading digits, mine doesn't. It works sometimes on mine apparently. It works with 1 or 2.[/EDIT]
• 03-05-2003
Trauts
Quote:

Originally posted by PJYelton
I think you need to add:
Code:

`++binCounters[place];`
after
Code:

`bins[place][binCounters[place]] = number;`
Otherwise you will keep writing over the zero spot in your bins.

I tried using that and it gives another illegal index.

By the way, I've tested it and using
++i is SLOWER than using i++ by a tiny amount. So if you need a speedier program, use i++
• 03-05-2003
Trauts
Reverse sorting...

There's the code... if you passed an array with all the integers 0 through 9 (In a random order), you'd end up sorted like this:

9
8
7
6
5
4
3
2
1
0

Also, if the collectBins() function is commented out, the program seems to function exactly the same, even though list isn't changed in any function but collectBins!

[EDIT]All right, the problem is in the addToBin() function... it is supposed to modify the bin counters, but it isn't. I tried incrementing the bincounter[place] like mentioned above, but that gave vector index problems

Code:

```// RADIXSORT.CPP #include <math.h> #include "apmatrix.h" #include "apvector.h" int const MAX_LIST_SIZE = 100; // Function: digit // Computes the kth digit in number // // Inputs: integers number and k // Outputs: the kth digit in number int digit(int number, int k) {         return (number/int(pow(10,k-1))) % 10; } // Function: initializeCounters // Initializes all bin counters to zero void initializeCounters(apvector<int> &binCounters) {         for (int i = 0; i < binCounters.length(); i++)                 binCounters[i] = 0; } // Function: addToBin // Insert number in bin structure, as indicated by place // // Inputs: a bin structure bins, a vector of bin counters, //                  a number, and a place // Outputs: bin structure bins and its vector of counters //                        have been altered to reflect addition of number //                        in bin eindexed by place template<class element> void addToBin(apmatrix<element> &bins,                           apvector<int> &binCounters, int number, int place) {         bins[place][binCounters[place]] = number; } // Function: collectBins // Append numbers in bins to list // // Inputs: list, a bin structure, and a vector of the counters for the //                        bin structure // Outputs: a list template<class element> void collectBins(apvector<element> &list, apmatrix<element> &bins,                                 apvector<int> &binCounters) {         //put everything back in one list         //matrix[row][column];         int row = 0;         int col = 0;         for (int i=0; i<list.length(); i++)         {                 //if (bins[row][col] < binCounters[row])                 //if (col < binCounters[row])                 if (binCounters[row] > 0/* && col < binCounters[row]*/)                 {                         list[i] = bins[row][col];                         if (col < bins[row].length())                                 col++;                 }                 else if (col == bins.numcols())                 {                         col = 0;                         //cout << row << " " << col << endl;                         if (row+1 < bins.numrows())                                 row++;                 }         } } // Function: radixSort // Sorts numbers in list into ascending order // // Inputs: list and its length // Outputs: the list with numbers sorted in ascending order template<class element> void radixSort(apvector<element> &list, int n) {         int j, k;         apmatrix<element> bins(10,MAX_LIST_SIZE);         apvector<int> binCounters(10);         initializeCounters(binCounters);         // For k loop controls digit used to classify data.         for (k = 1; k <= 4; k++)         {                 // For j loop iterates through all numbers, putting them into                 // bin determined by kth digit.                 for (j = 0; j < n; j++)                         addToBin (bins, binCounters, list[j], digit(list[j], k));                 collectBins (list, bins, binCounters);                 initializeCounters(binCounters);         } }```
• 03-05-2003
PJYelton
Do you understand EXACTLY how radix sort works? If so, then you shouldn't have a problem debugging your code. Just go step by step and testing it to make sure that it is doing what it is supposed to.

You need binsCounter[place]++ to increment the values, otherwise when you place the numbers into the bins, they will constantly be overwritten at the zero spot. Think about, if its not in there then, then why do you even both constantly initializing them, they will always be zero!

Quote:

By the way, I've tested it and using
++i is SLOWER than using i++ by a tiny amount. So if you need a speedier program, use i++
Thats funny, I've tested it to and I got the opposite results. Oh well, doesn't matter, the difference is so small that its negligible.
• 03-05-2003
Trauts
Quote:

Originally posted by Trauts
I tried using that and it gives another illegal index.
weird... must depend on the compiler with ++i and i++

Besides, when I did what you said (I realized I needed that after I relooked at my function, but your code would have helped), only it doesn't work: it gives this:

illegal vector index: -5 max index = 9;

And in the debugger, if I try to display what binCounters[place] is, it gives this:

binCounters[place] CXX0034: Error: types incompatible with operator

Where the [place] SHOULD be returning an integer. It doesn't give me that problem unless I use the debugger, but thats obviously why the code isn't working.
• 03-05-2003
PJYelton
Sounds like there is something wrong with the integer place... add this right above your code in the addToBin:
Code:

```cout<<place<<endl; cout<<binCounters[place]<<endl;```
• 03-05-2003
Trauts
I think it might actually be the collectbins function. I rewrote it on a piece of scrap paper, I'll try it tomarrow. Thanks.

If you look at it, it isn't really good to do it in one loop, you need nested ones.
• 03-05-2003
Trauts
Quote:

Originally posted by PJYelton
Sounds like there is something wrong with the integer place... add this right above your code in the addToBin:
Code:

```cout<<place<<endl; cout<<binCounters[place]<<endl;```

I don't think it could be place because I can cout just fine the value of it, and the debugger can see it.
• 03-05-2003
PJYelton
If you put in the couts like I said, what does place and binCounters[place] equal just before the invalid index error?

Your collectbins needs to be something like (in pseudocode):
Code:

```for (int x=0; x<10; x++) {     for (int y=0; y<binCounters[x]; y++)     {         add bins[x][y] to the list     } }```
• 03-05-2003
rmullen3
~
"By the way, I've tested it and using
++i is SLOWER than using i++ by a tiny amount. So if you need a speedier program, use i++"

While the computer is a strange animal, I don't see why postfix would be any faster at all...
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last