Radix sort algoritm - jgrigorjeva/push_swap GitHub Wiki

How do we adapt the radix sort algorithm to the push_swap project?

Step 1: Normalize the input

We need to replace each number by its order (indice) in a sorted list. Example:

Original A = [12,5,8,2]
Sorted order = [2, 5, 8, 12]
Indices = [3, 1, 2, 0]
A becomes [3,1,2,0]

Why normalize? The sorting will be done based on bits, so it is easier to start from 0 rather than to handle some negative numbers that may appear in the input. There are some more advantages, you will see at the end ;). After all, we do not need to return the original ordered list, just the sequence of operations to order it.

Step 2: Iterate Over Each Bit

Iterate over each bit: we start from the least significant bit (LSB) and move left by one bit, process that, and repeat until we reach the most significant bit of the largest number (indice). Therefore, we need to calculate the number of bits we are going to iterate over. E.g. if the largest indice is 99 (we have 100 numbers), 99 in binary is 1100011 (7 digits), so there will be 7 iterations.

Step 2.5: In each iteration: Sort Numbers by Bits

We are going to push the numbers with smaller bit over to B. So for each bit (starting from LSB) we are looking at the bit value (0 or 1), if it is 0, the number is pushed to B. If the bit value is 1, the number is kept in A, and A rotated or reverse rotated to get to the next number to be pushed to B. Then all the numbers from B are pushed back to A. Then move to the next bit to sort.

Why does the Radix Sort Algorithm work

Let's see an example first. Consider sorting the numbers [6,3,5,2] by their binary representation:

Binary:
    6 = 110
    3 = 011
    5 = 101
    2 = 010

In the first iteration, numbers with zero LSB will be pushed to B (6 = 110, 2 = 010) and back to A. Therefore, stack A after the first iteration is

[110, 010, 011, 101] = [6, 2, 3, 5]

In the second iteration we are looking at the middle bit, so 101 will be pushed to B and back to A. The stack A after the second iteration will be

[101, 110, 010, 011] = [5, 6, 2, 3]

In the last iteration, we push based on the most significant bit, so 011 and 010 (in this order) will be pushed to B and back. The stack A after the second iteration will be

[010, 011, 101, 110] = [2, 3, 5, 6]

Now you can see that when moving from the least significant digit to the most significant digit: 1. All elements with the same current bit value (0 or 1) are grouped together during that iteration. 2. Within these groups, the earlier sorting by lower-order bits is preserved. This is because the only operations used in this algorithm are the rotate (or reverse rotate) and push. By using swap, the relative order achieved by previous sorting would be lost!

Ups, have you noticed? I forgot to normalize the data. This has actually added some unnecessary operations to the result. Let's see what happens when normalized data are fed to the Radix sort algorithm.

The normalized version

Let's replace our the original values by their indices (and their binary representations):

6 -> 3 = 11

3 -> 1 = 01

5 -> 2 = 10

2 -> 0 = 00

See? We have already reduced the bits to iterate over. Now in the first iteration 00 and 10 will be pushed to B and back, so A will become [00, 10, 11, 01]. In the second iteration, 00 and 01 will be pushed to B and back, so A becomes [00, 01, 10, 11]. Congratulations, the list is sorted!

Possible optimizations

1. Start the next iteration before pushing to A

Instead of pushing everything from stack A to stack B at the end of the first iteration, start new iteration here (with numbers in stack B). Push to A selectively only the numbers that contain 1 in the second least significant bit. After processing the whole stack B this way, continue the current iteration in the stack A and push to B numbers containing 0 in the current bit. This will save you some unnecessary pushing between stacks. Continue this way with every remaining iteration.

2. Two or more bit sorting

Instead of selecting the numbers to push based on one bit value (0 or 1), divide the numbers according to their two bit values: 00, 01, 10 and 11. The largest value (11) should remain in the stack A, whereas all numbers containing 00 should be pushed to B first, then 01 second and 10 last. This, in theory, should reduce the number of unnecessary operations, but the results I got with this modification were even worse than the original.