Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I need a little help understanding the implementation of radix exchange sort algorithm.

Radix exchange (I don't know if it's the exact name in english based literature) is a lot similar to quicksort, but uses binary representation of numbers.

Firts we look the highest digit in binary representation, and then using two indexes (from the beginning of the array and from the end, we increment the first if the given digit is 0, and decrement the other if the given digit is 1). Then we swap two numbers, and then continue the work until i = j (the indexes are equal). Then we have two separate partitions and sort them using the second most important digit and so on...

Mainly, I have a few questions:

  1. Is this algorithm really called radix exchange or does it have some other, more commonly used name?

  2. What are the advantages of this algorithm? It seems like a lot of work, and not very effective?

  3. Where can I see an example of implementation of the algorithm? Maybe it will be a little more clearer on what it really is, because it's really confusing for me at the moment.

share|improve this question

2 Answers 2

it sounds like the time complexity would be O(n*k) and space complexity is O(k) with k being the number of bits of each element

in C++ it would be

radixQsort(int* arrb, int* arre, int rad=INT_BITS){
    if(arrb==arre)return;

    int* arrm = std::partition(arrb,arre,[rad](a){return !(a&(1<<rad));});

    radixQsort(arrb,arrm,rad-1);
    radixQsort(arrm,arre,rad-1);
}

this is implemented using the partition in the standard library which works like the partition you described

share|improve this answer
  1. In contrast to quick-sort, radix sort uses "internal representation" of the values which are sorted. I.e. it doesn't simply compare them with < >. And it is really effective when you take several bits, not one, on each sorting pass. 4 bits, maybe 8. So you will divide the array onto 256 groups on each pass in the latter case. And have only 4 passes for 32-bit integers.

https://en.wikipedia.org/wiki/Radix_sort

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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