radix sort using queues

[pepstein]

My program takes an unsorted array and then sorts in using radix sort. the radix sort uses an array of queues, one per possible digit and then runs through each digit and places it back into the array until all place values are run through and thus the array is sorted. Right now it the sort doesn't run properly, it spits out improper values, I believe it has something to do with how I am placing them back into the array. Any help would be appreciated, thanks.

  #include <iostream>
#include <queue>
#include <ctime>
#include <cstdlib>
using namespace std;

int *radixSort(int q[]);

int main() {
    const int MAX=1000;
    int radix[MAX], *sortedRadix;
    int seed =time(0);
    srand(seed);


    //fill array with random #s
    for (int i=0;i<MAX;i++){
        int num=0+rand()%MAX;
        radix[i]=num;
    }
    //print unsorted
    for (int j=0;j<MAX;j++)
        cout << radix[j] << " ";
    cout << endl << endl;
    //radix sort
    sortedRadix=radixSort(radix);
    //print sorted
    for (int j=0;j<MAX;j++)
        cout << sortedRadix[j] << " ";

    cout << endl <<endl;
    cout<<"flag";


return 0;
}

int *radixSort(int q[]) {
    queue<int> bins[10]; //one array per possible digit
    int maxDigits=3; //holds amount of digits in largest number
    int currentDigit=1; //right most digit
    int a[1000]; //holds numbers during sort

    while (currentDigit <= maxDigits) {
        for(int i=0; i<1000; i++){ //loop through whole array
            int num = q[i]; //set to current value of array position
            int digitValue = static_cast<int>(num/currentDigit)%10; //get the decimal digit at current digit
            bins[digitValue].push(num); //put digits in corresponding bins
        }
        //Transfer results of bins back into main array
    	for (int i=0; i<1000; i++){
            for(int k=0;k<10;k++){ //loop through all bins
                while (!bins[k].empty()){ //push all elements in bin[k] until empty to a
                    int temp=bins[k].front();
                    a[i]=temp;
                    bins[k].pop();
                }
            }
        }
    currentDigit++;
    }
return a;
}

[pepstein]

still not sure what I'm doing wrong, is anyone able to see my error?

[pepstein]

also, is my way of getting the digit incorrect? I believe it may be but I can't figure out the proper way

[Duthomhas]

You can't return a local variable (a).

Why not modify q directly?

[pepstein]

i've tried doing that and it doesn't work either in the code's current form, although that is how I am implementing currently. i think the problem lies in how I am putting the data into the array, ie the loops don't function as i'd like them to.

[norm b]

also, is my way of getting the digit incorrect?

Yes. Your divisor should be multiples of 10.

789/1 % 10 = 9     
789/10 % 10 = 8				
789/100 % 10 = 7			

not    	
789/1 % 10 = 9
789/2 % 10 = 4
789/3 % 10 = 3

line 46 - you're retrieving a number from the original array "q" not your partially sorted array "a". Following Duoas' suggestion to modify q directly should solve this.

line 55 - you put all 10 numbers from your "bin" into one location.

HTH

[Duthomhas]

No, it doesn't work because you can't return a local variable.

The other issue is that your algorithm makes some numerical mistakes.

(1)
On line 47, you are dividing by currentDigit, when you should be dividing by 10**currentDigit. Use the std::pow() function to calculate ten to a power (#include <cmath>).

Once you fix that, you'll also have to adjust your indexing: 10¹ is 10, so you want currentDigit to start at 0. You'll also want to change the condition on line 44 to strictly less-than.

(2)
The next problem is how you are peeling numbers out of your bins. Your counter loop on line 51 causes i to remain the same all during the inner loops (lines 52 through 57). Get rid of line 51's loop and just set int i = 0;. Don't forget to increment i somewhere around line 55.

(3)
Okay, this is just to reiterate. Get rid of all the a[i]'s and replace them with q[i]'s, and get rid of line 42.

(4)
Your sort algorithm assumes that there will be 1000 numbers in your array. It also doesn't actually have to return a value. I recommend you change its prototype to:

    void radixSort(int q[], int n)

Then you can call it in main() this way:

int main() {
    const int MAX=1000;
    int data[MAX];
    ...

    radixSort(data,MAX);
    ...

    for (int j=0;j<MAX;j++)
        cout << data[j] << " ";
    ...

By the way, I'm impressed you used an array of ten std::queue for your base-10 radix sort. Very nice!

Hope this helps.

[pepstein]

Great, thanks for all the info that definitely helped. Just about have it but my output prints out a little bit off with some the numbers in the 90's being switched around. Any idea why this is happening?

void radixSort(int q[], int n) {
    queue<int> bins[10]; //one array per possible digit
    int maxDigits=3; //holds amount of digits in largest number
    int currentDigit=0; //starting base for decimal digit


    while (currentDigit < maxDigits) {
        for(int i=0; i<n; i++){ //loop through whole array
            int divisor=pow(10,currentDigit);
            int num = q[i]; //set to current value of array position
            int digitValue = static_cast<int>((num/divisor)%10); //get the decimal digit at current digit
            bins[digitValue].push(num); //put digits in corresponding bins
        }

        //Transfer results of bins back into main array{
            int i=0;
            for(int k=0;k<10;k++){ //loop through all bins
                while (!bins[k].empty()){ //push all elements in bin[k] until empty to a
                    int temp=bins[k].front();
                    q[i]=temp;
                    bins[k].pop();
                    i++;
                }
            }
    currentDigit++;
    }

output (w/o unsorted list to save space]

Printing sorted list...
0 1 2 2 3 4 4 4 4 5 6 7 9 12 13 13 13 15 17 18 18 19 19 19 19 20 22 23 23 23 24
25 28 29 30 31 35 36 37 38 40 41 41 42 43 43 43 44 46 46 47 49 50 51 53 54 54 54
 55 58 58 58 59 59 61 62 64 65 66 67 69 69 72 72 72 72 73 73 73 73 74 74 74 75 7
7 78 78 79 80 85 87 89 89 89 90 990 92 92 993 993 94 94 995 995 995 96 96 996 97
 997 97 97 998 998 98 100 105 106 106 106 106 108 109 112 112 115 116 119 120 12
2 122 123 124 124 126 126 126 129 129 129 130 132 133 135 136 138 139 140 141 14
1 142 142 142 143 143 144 144 145 145 145 145 146 148 149 149 150 151 152 153 15
3 153 156 157 159 159 159 160 161 162 163 163 164 164 164 166 166 167 168 171 17
2 174 174 175 179 179 182 182 183 184 184 184 184 184 184 184 185 187 187 190 19
2 194 195 196 196 197 197 197 99 200 201 201 201 202 202 205 205 206 206 206 207
 208 210 213 213 213 213 214 215 215 217 217 218 218 219 220 222 224 225 225 226
 226 226 228 228 229 230 231 233 233 235 236 236 236 237 239 239 240 240 241 242
 243 244 247 247 248 249 250 251 255 258 259 259 262 264 265 266 267 269 274 276
 276 276 277 278 280 280 280 281 281 287 288 291 291 292 294 294 295 295 296 296
 199 199 301 304 304 304 305 306 307 308 309 310 311 312 312 313 314 315 315 315
 318 318 318 318 319 320 321 321 321 322 323 323 324 325 326 330 331 333 335 335
 336 336 337 338 339 339 341 341 342 342 343 344 344 345 349 350 355 356 356 356
 356 357 359 361 362 362 366 366 367 368 368 368 368 369 370 372 374 375 376 376
 376 376 376 377 378 379 379 380 381 381 384 384 385 385 387 391 391 392 393 394
 395 297 299 299 402 402 404 405 405 406 407 407 408 408 410 411 411 412 412 416
 416 417 418 419 421 421 421 424 424 425 425 426 427 427 428 428 429 429 429 430
 432 433 433 434 436 441 441 442 443 447 447 447 448 448 448 450 450 452 454 455
 457 458 458 459 460 461 462 465 466 467 467 469 469 469 469 470 472 473 474 475
 477 479 480 482 483 484 487 487 488 490 493 494 494 396 397 398 399 399 501 501
 504 505 505 505 506 507 507 508 510 510 511 513 515 515 516 517 519 519 519 520
 522 522 523 524 526 526 527 528 529 530 531 532 533 533 534 535 537 538 538 539
 540 542 544 544 546 547 547 548 549 550 550 551 552 553 554 555 555 557 558 558
 559 559 560 560 561 562 562 564 565 568 569 569 569 571 572 573 574 575 576 577
 578 579 579 580 581 582 582 582 584 584 586 587 587 589 589 591 591 591 495 499
 600 600 601 606 606 610 610 611 611 614 617 617 618 619 619 621 622 622 625 625
 627 629 629 629 630 631 633 633 634 636 637 639 640 641 642 642 643 644 646 646
 646 646 646 647 647 648 649 650 650 651 652 653 654 654 655 656 656 657 658 658
 659 660 660 661 662 666 667 667 667 668 668 668 669 669 670 670 671 671 672 673
 674 675 676 678 679 679 680 683 683 683 683 683 685 686 686 687 689 689 690 692
 692 594 594 594 595 595 595 596 596 596 598 598 700 702 702 704 705 708 711 711
 711 713 714 714 715 715 715 715 715 716 717 717 718 719 720 720 722 722 723 727
 727 729 729 731 732 732 733 733 735 738 738 739 739 742 745 747 747 747 748 748
 748 748 749 752 752 754 754 754 755 758 760 761 764 764 765 766 767 768 769 770
 773 775 777 778 779 779 780 782 783 785 788 788 789 791 693 695 698 698 800 801
 801 802 806 810 811 815 816 817 817 817 818 818 822 825 825 827 828 828 829 831
 833 833 836 836 836 838 838 840 840 840 841 844 844 844 848 848 853 853 854 856
 856 856 859 859 862 864 866 866 867 868 872 872 872 873 874 875 876 877 877 877
 877 879 881 882 882 883 885 885 886 886 886 887 889 889 889 890 792 792 793 796
 796 798 799 799 900 900 900 900 901 901 902 902 902 903 905 905 906 907 907 910
 911 912 914 914 915 915 915 917 918 918 919 919 919 922 923 925 926 928 931 931
 931 932 932 934 935 935 937 938 938 940 941 942 942 943 949 950 951 951 953 953
 954 955 960 961 961 962 963 963 963 963 963 964 964 964 966 968 969 971 972 972
 974 974 975 976 976 977 977 978 979 981 984 984 986 987 987 989 891 892 892 894
 894 895 895 896 896 896 896 897 898 898


Process returned 0 (0x0)   execution time : 0.646 s
Press any key to continue.

[norm b]

Your revised code works fine on my machine. Are you using an IDE. If so try cleaning your project.

void radixSort(int q[], int n);

int main() {
  const int MAX=1000;
  int radix[MAX], *sortedRadix;
  int seed =time(0);
  srand(seed);
  for (int i=0;i<MAX;i++){
      int num=0+rand()%MAX;
      radix[i]=num;
  }
  for (int j=0;j<MAX;j++)
      cout << radix[j] << " ";
  cout << endl << endl;
  radixSort(radix, MAX);
  for (int j=0;j<MAX;j++)
      cout << radix[j] << " ";
  cout << endl <<endl;
return 0;
}

void radixSort(int q[], int n) {
    queue<int> bins[10]; //one array per possible digit
    int maxDigits=3; //holds amount of digits in largest number
    int currentDigit=0; //starting base for decimal digit
    while (currentDigit < maxDigits) {
        for(int i=0; i<n; i++){ //loop through whole array
            int divisor=pow(10,currentDigit);
            int num = q[i]; //set to current value of array position
            int digitValue = static_cast<int>((num/divisor)%10); //get the decimal digit at current digit
            bins[digitValue].push(num); //put digits in corresponding bins
        }
        int i=0;
        for(int k=0;k<10;k++){ //loop through all bins
            while (!bins[k].empty()){ //push all elements in bin[k] until empty to a
                int temp=bins[k].front();
                q[i]=temp;
                bins[k].pop();
                i++;
            }
        }
        currentDigit++;
    }
}

[pepstein]

i was running it on an IDE but just ran it on cygwin and it worked, thanks