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\$
4
  • \$\begingroup\$ What is the question, whether your implementation of the algorithm is correct? whether the asymptotic costs are the ones of algorithm? \$\endgroup\$ Mar 17, 2013 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, 2013 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, 2013 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\$ Mar 18, 2013 at 6:15

1 Answer 1

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\$
3
  • \$\begingroup\$ thanks for the answer. can you also answer the second part of the question ? \$\endgroup\$
    – bysreg
    Mar 23, 2014 at 6:10
  • 1
    \$\begingroup\$ Wikipedia says radix sort uses O(k + n) space. I challenge you to do better than conventional wisdom. ☺ \$\endgroup\$ Mar 23, 2014 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, 2014 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.