Algorithm for sorting an array with 4 options

Question

I was given a task to sort an array that is filled with (non negative) integers.

They should be sorted such that the output is in the following order:

Numbers where the remainder of them divided by 4 is 0
Numbers where the remainder of them divided by 4 is 1
Numbers where the remainder of them divided by 4 is 2
Numbers where the remainder of them divided by 4 is 3

I tried to write a simple algorithm that should work at O(n) (the task is to write the code efficiently).

But I think it's a mess, a few cases didn't work (for example when I tried an array where the first few numbers have remainders of 3).

Any suggestion on how to fix it or a better way of doing this?

public static void sortByFour(int[] arr)
{
    int zeroR = -1, oneR = 0, twoR = arr.length-1, threeR = arr.length;

    do
    {
        if (arr[oneR]%4==1)
         oneR++;
        else if (arr[oneR]%4==0)
        {
            zeroR++;
            int temp = arr[oneR];
            arr[oneR] = arr[zeroR];
            arr[zeroR] = temp;
            oneR++;
        }
        else if (arr[oneR]%4==2)
        {
            twoR--;
            int temp = arr[oneR];
            arr[oneR] = arr[twoR];
            arr[twoR] = temp;
        }
        else if (arr[oneR]%4==3)
        {
            threeR--;
            int temp = arr[oneR];
            arr[oneR] = arr[threeR];
            arr[threeR] = temp;
        }
    } while (oneR < threeR && oneR < twoR);
}

amit · Accepted Answer · 2014-04-01T12:12:18.600

A bucket sort can do the trick for you. Note that you can overcome the O(n) extra space factor of bucket sort by looping 4 times (once per each reminder), something like (java-like pseudo code):

final int REMINDER = 4; //4 because you use %4
int curr = -1;
for (int r = 0; r < REMINDER ; r++) { 
   for (int i = curr + 1; i < arr.length; i++) { 
       if (arr[i] % REMINDER  == r) { 
          //swap elements:
          int temp = arr[i];;
          arr[i] = arr[++curr];
          arr[curr] = temp;
       }
   }
}

The idea is to 'remember' where you have last set element, and iterate the array 4 times, and swap elements with matching reminder to the desired location (which you remembered).

Complexity is still O(n) with O(1) extra space.

An alternative is O(n) (but much better constants) time with O(n) space is to use a classic bucket sort, with a single pass store all elements in 4 different lists according to the desired reminder, and in a 2nd pass - on those 4 lists, fill the original array with the elements according to the desired order.

Nice idea. The only disadvantage of the in-place method is that it isn't stable, while bucket sort is stable. — Eyal Schneider, Apr 01 '14 at 12:10
It's "remainder", not "reminder" (corrected in question), but "divisor" seems like a more appropriate variable name for your code (otherwise I would've edited it myself). — Bernhard Barker, Apr 01 '14 at 14:06
sorry for the beginner question but why this doesn't work with "curr++"? nevermind got it from http://stackoverflow.com/questions/484462/difference-between-i-and-i-in-a-loop — Seth Keno, Apr 01 '14 at 17:20

Algorithm for sorting an array with 4 options

1 Answers1