Sorting: how to sort an array that contains 3 kind of numbers

Question

For example: int A[] = {3,2,1,2,3,2,1,3,1,2,3};

How to sort this array efficiently?

This is for a job interview, I need just a pseudo-code.

Answer 1

As robert mentioned basketsort (or bucketsort) is the best in this situation.

I would also added next algorithm (it's actually very similar to busket sort):

[pseudocode is java-style]

Create a HashMap<Integer, Interger> map and cycle throught your array:

for (Integer i : array) {
    Integer value = map.get(i);
    if (value == null) {
        map.put(i, 1);
    } else {
        map.put(i, value + 1);
    }
 }

Answer 2

I would use a recursive approach over here

fun sortNums(smallestIndex,largestIndex,array,currentIndex){
if(currentIndex >= array.size)
   return
if (array[currentIndex] == 1){
You have found the smallest element, now increase the smallestIndex
//You need to put this element to left side of the array at the smallestIndex position.
//You can simply swap(smallestIndex, currentIndex)
// The catch here is you should not swap it if it's already on the left side
//recursive call
sortNums(smallestIndex,largestIndex,array,currentIndex or currentIndex+1)// Now the task of incrementing current Index in recursive call depends on the element at currentIndex. if it's 3, then you might want to let the fate of currentIndex decided by recursive function else simply increment by 1 and move further
} else if (array[currentInde]==3){
// same logic but you need to add it at end
}
}

You can start the recursive function by sortNums(smallestIndex=-1,largestIndex=array.size,array,currentIndex=0)

You can find the sample code over here Code Link

Answer 3

def DNF(input,length):
    high = length - 1
    p = 0
    i = 0
    while i <= high:
            if input[i] == 0:
                    input[i],input[p]=input[p],input[i]
                    p = p+1
                    i = i+1
            elif input[i] == 2:
                    input[i],input[high]=input[high],input[i]
                    high = high-1
            else:
                    i = i+1
input = [0,1,2,2,1,0]
print "input: ", input
DNF(input,len(input))
print "output: ", input

Answer 4

//Bubble sort for unsorted array - algorithm
public void  bubleSort(int arr[], int n) { //n is the length of an array
    int temp;
    for(int i = 0; i <= n-2; i++){
        for(int j = 0; j <= (n-2-i); j++){
            if(arr[j] > arr[j +1]){
                temp = arr[j];
                arr[j] = arr[j +1];
                arr[j + 1] = temp;

            }
        }

    }

Answer 5

This can be done very easily using-->

Dutch national Flag algorithm http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

instead of using 1,2,3 take it as 0,1,2

Answer 6

Lets break the problem we have just two numbers in array . [1,2,1,2,2,2,1,1]

We can sort in one pass o(n) with minm swaps if; We start two pointers from left and right until they meet each other. Swapping left element with right if left element is bigger. (sort ascending)

We can do another pass, for three numbers (k-1 passes). In pass one we moved 1's to their final position and in pass 2 we moved 2's.

def start = 0, end = array.size() - 1;

// Pass 1, move lowest order element (1) to their final position 
while (start < end) {
    // first element from left which is not 1
    for ( ; Array[start] ==  1 && start < end ; start++);
    // first element from right which IS 1
    for ( ; Array[end] != 1 && start < end ; end--);

    if (start < end) swap(start, end);
}     

// In second pass we can do 10,15

// We can extend this using recurion, for sorting domain = k, we need k-1 recurions 

Answer 7

Here is the groovy solution, based on @ElYusubov but instead of pushing Bucket(5) to beginning & Bucket(15) to end. Use sifting so that 5's move toward beginning and 15 towards end.

Whenever we swap a bucket from end to current position, we decrement end, do not increment current counter as we need to check for the element again.

array = [15,5,10,5,10,10,15,5,15,10,5]

    def swapBucket(int a, int b) {

        if (a == b) return; 
        array[a] = array[a] + array[b]
        array[b] = array[a] - array[b]
        array[a] = array[a] - array[b]

    }

def getBucketValue(int a) {
    return array[a];
}

def start = 0, end = array.size() -1, counter = 0;
// we can probably do away with this start,end but it helps when already sorted.

// start - first bucket from left which is not 5
while (start < end) {

    if (getBucketValue(start) != 5) break;
    start++;

}     

// end - first bucket from right whichis not 15
while (end > start) {

    if (getBucketValue(end) != 15) break;
    end--;

}

// already sorted when end = 1 { 1...size-1 are Buck(15) } or start = end-1      

for (counter = start; counter < end;) {

    def value = getBucketValue(counter)

    if (value == 5) { swapBucket(start, counter); start++; counter++;}
    else if (value == 15) { swapBucket(end, counter); end--; } // do not inc counter
    else { counter++; }

}

for (key in array) { print " ${key} " }

Answer 8

Just for fun, here's how you would implement "pushing values to the far edge", as ElYusubub suggested:

sort(array) {
  a = 0
  b = array.length
  # a is the first item which isn't a 1 
  while array[a] == 1
    a++
  # b is the last item which isn't a 3
  while array[b] == 3
    b--

  # go over all the items from the first non-1 to the last non-3
  for (i = a; i <= b; i++)
    # the while loop is because the swap could result in a 3 or a 1
    while array[i] != 2
      if array[i] == 1
        swap(i, a)
        while array[a] == 1
          a++
      else # array[i] == 3
        swap(i, b)
        while array[b] == 3
          b--

This could actually be an optimal solution. I'm not sure.

Answer 9

The promising way how to sort it seems to be the counting sort. Worth to have a look at this lecture by Richard Buckland, especially the part from 15:20.

Analogically to the counting sort, but even better would be to create an array representing the domain, initialize all its elements to 0 and then iterate through your array and count these values. Once you know those counts of domain values, you can rewrite values of your array accordingly. Complexity of such an algorithm would be O(n).

Here's the C++ code with the behaviour as I described it. Its complexity is actually O(2n) though:

int A[] = {3,2,1,2,3,2,1,3,1,2,3};
int domain[4] = {0};

// count occurrences of domain values - O(n):  
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
    domain[A[i]]++;

// rewrite values of the array A accordingly - O(n):    
for (int k = 0, i = 1; i < 4; ++i)
    for (int j = 0; j < domain[i]; ++j)
        A[k++] = i;

Note, that if there is big difference between domain values, storing domain as an array is inefficient. In that case it is much better idea to use map (thanks abhinav for pointing it out). Here's the C++ code that uses std::map for storing domain value - occurrences count pairs:

int A[] = {2000,10000,7,10000,10000,2000,10000,7,7,10000};
std::map<int, int> domain;

// count occurrences of domain values:  
int size = sizeof(A) / sizeof(int);
for (int i = 0; i < size; ++i)
{
    std::map<int, int>::iterator keyItr = domain.lower_bound(A[i]);
    if (keyItr != domain.end() && !domain.key_comp()(A[i], keyItr->first))
        keyItr->second++; // next occurrence 
    else
        domain.insert(keyItr, std::pair<int,int>(A[i],1)); // first occurrence
}

// rewrite values of the array A accordingly:    
int k = 0;
for (auto i = domain.begin(); i != domain.end(); ++i)
    for (int j = 0; j < i->second; ++j)
        A[k++] = i->first;

(if there is a way how to use std::map in above code more efficient, let me know)

Answer 10

I think I understasnd the question - you can use only O(1) space, and you can change the array only by swapping cells. (So you can use 2 operations on the array - swap and get)

My solution:

Use 2 index pointers - one for the position of the last 1, and one for the position of the last 2.

In stage i, you assume that the array is allready sorted from 1 to i-1, than you check the i-th cell: If A[i] == 3 you do nothing. If A[i] == 2 you swap it with the cell after the last 2 index. If A[i] == 1 you swap it with the cell after the last 2 index, and than swap the cell after the last 2 index (that contains 1) with the cell after the last 1 index.

This is the main idea, you need to take care of the little details. Overall O(n) complexity.

Answer 11

Its a standard problem in computer science : Dutch national flag problem See the link.

Answer 12

Problem description: You have n buckets, each bucket contain one coin , the value of the coin can be 5 or 10 or 20. you have to sort the buckets under this limitation: 1. you can use this 2 functions only: SwitchBaskets (Basket1, Basket2) – switch 2 baskets GetCoinValue (Basket1) – return Coin Value in selected basket 2. you cant define array of size n 3. use the switch function as little as possible.

My simple pseudo-code solution, which can be implemented in any language with O(n) complexity.

I will pick coin from basket 1) if it is 5 - push it to be the first, 2)if it is 20- push it to be the last, 3)If 10 - leave it where it is. 4) and look at the next bucket in line.

Edit: if you can't push elements to the first or last position then Merge sort would be ideally for piratical implementation. Here is how it will work:

Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n). Merge sort has seen a relatively recent surge in popularity for practical implementations, being used for the standard sort routine in the programming languages

Answer 13

This code is for c#:

However, you have to consider the algorithms to implement it in a non-language/framework specific way. As suggested Bucket set might be the efficient one to go with. If you provide detailed information on problem, i would try to look at best solution. Good Luck...

Here is a code sample in C# .NET

int[] intArray = new int[9] {3,2,1,2,3,2,1,3,1 };
Array.Sort(intArray);
// write array
foreach (int i in intArray) Console.Write("{0}, ", i.ToString());  

Answer 14

count each number and then create new array based on their counts...time complexity in O(n)

 int counts[3] = {0,0,0};
 for(int a in A)
  counts[a-1]++;
 for(int i = 0; i < counts[0]; i++)
  A[i] = 1;
 for(int i = counts[0]; i < counts[0] + counts[1]; i++)
  A[i] = 2;
 for(int i = counts[0] + counts[1]; i < counts[0] + counts[1] + counts[2]; i++)
  A[i] = 3;

Answer 15

Have you tried to look at wiki for example? - http://en.wikipedia.org/wiki/Sorting_algorithm

Answer 16

I think the question is intending for you to use bucket sort. In cases where there are a small number of values bucket sort can be much faster than the more commonly used quicksort or mergesort.