6
\$\begingroup\$

I am trying to implement a stable radix sort in place with O(1) space. I've seen Wikipedia, and I notice the C implementation is using a temporary variable to hold the sorted value for each pass, and the section of "in-place" MSD radix sort implementation is quite confusing.

I took the C code and tried to implement it in C++ for the stable in-place radix sort version:

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

void radix_sort(vector<int>& v) {
    //search for maximum number
    int max_number = v[0];
    for(int i = 1;i<v.size();i++) {
        if(max_number < v[i])
            max_number = v[i];
    }

    int bucket[10]; // store first index for that digit
    int bucket_max_index[10]; // store maximum index for that digit 
    int exp = 1;

    while(max_number / exp > 0) {           
        memset(bucket, 0, 10 * sizeof(int));        
        memset(bucket_max_index, 0, 10 * sizeof(int));      
        for(int i=0;i<v.size();i++) {
            bucket[(v[i] / exp) % 10]++;                        
        }       

        int index = v.size();
        for(int i=9;i>=0;i--) {
            index -= bucket[i];
            bucket_max_index[i] = index + bucket[i];
            bucket[i] = index;                      
        }   

        index = 0;
        vector<int> temp(v.size());
        for(int i=0;i<v.size();i++) {
            int digit = (v[i] / exp) % 10;  
            temp[bucket[digit]] = v[i];         
            bucket[digit]++;
        }

        for(int i=0;i<v.size();i++) {
            v[i] = temp[i];
        }       

        exp *= 10;
    }
}

EDIT:

Thanks to the comments, I checked and found out that I made a mistake. The original idea of the question is that I want to implement a stable in-place radix sort.

I thought I succeeded in implementing it when I tested it with a several test cases (one of them is this test case: {1, 3, 2, 5, 8, 2, 3, 1}) .

I changed the code to a stable radix sort with O(n) space and changed my questions to:

  1. Is this O(kn) time ? (with k as the maximum number of digits)

  2. Can we improve the above code to be a stable radix sort with O(1) space ?

\$\endgroup\$
  • \$\begingroup\$ What is the question, whether your implementation of the algorithm is correct? whether the asymptotic costs are the ones of algorithm? \$\endgroup\$ – David Rodríguez - dribeas Mar 17 '13 at 2:15
  • \$\begingroup\$ @David: That's the way I understand it... "Does this code correctly sort inputs?" and "Is the stable radix sort algorithm (which implies its memory and runtime complexity) implemented by this code?" \$\endgroup\$ – Ben Voigt Mar 17 '13 at 2:43
  • \$\begingroup\$ @DavidRodríguez-dribeas yes, i was asking if this code is correct and whether the time complexity is O(kn) and the space complexity is O(1) \$\endgroup\$ – bysreg Mar 17 '13 at 3:16
  • \$\begingroup\$ @DavidRodríguez-dribeas: This is code review. You are supposed to read and comment on the codes design/maintainability anything else that is important. \$\endgroup\$ – Martin York Mar 18 '13 at 6:15
3
\$\begingroup\$

Yes, your radix sort appears to be correct, and runs in O(k n) time.

bucket_max_index is written to, but otherwise never used. You can eliminate it completely.

Before the creation of the temp vector, you set index = 0. It would be clearer to change that to assert(index == 0), since that should have been the result of v.size() - Σ bucket[i] in the previous loop.

\$\endgroup\$
  • \$\begingroup\$ thanks for the answer. can you also answer the second part of the question ? \$\endgroup\$ – bysreg Mar 23 '14 at 6:10
  • 1
    \$\begingroup\$ Wikipedia says radix sort uses O(k + n) space. I challenge you to do better than conventional wisdom. ☺ \$\endgroup\$ – 200_success Mar 23 '14 at 6:13
  • \$\begingroup\$ Well, I guess for now, stable radix sort uses O(k+n) space. You would have to lose the stable property to achieve the O(1) space. \$\endgroup\$ – bysreg Mar 23 '14 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.