sorting array of (1,2,3) numbers in O(n) time

Question

Given a list of numbers with only 3 unique numbers(1, 2, 3), sort the list in O(n) time. Plus sort the array using constant space O(1).

Example:

Input: [3, 3, 2, 1, 3, 2, 1]

Output: [1, 1, 2, 2, 3, 3, 3]

Here the solution i made (is no O(1) space and have empty spaces spaces in the array..): What does this function is simple .. increases the size of the arrangement to double in the case that all its elements are 2; Then it goes to its previous length (current/2) to sort its elements .. if it is 1 it does nothing, if it finds a 2 it puts it in the previous maximum length + 1, it increases the variable len and eliminates the element and if it is 3 push and delete the element .. then you have empty spaces in the array and you don't meet the plus of the problem but it's O(n).

function sort(list) {
    let len = list.length;
    list.length=len*2
    for(let i=0; i<list.length/2; i++){
        let n=list[i]
        if(n==2){
            list[len]=n
            delete list[i]
            len++
        }else if(n==3){
            list.push(n)
            delete list[i]
        }
    }
    return list
}

console.log(sort([1,2,3,2,1,1]))

Answer 1

You could use the algorithm of the Dutch national flag problem:

The Dutch national flag problem ¹ is a computer science programming problem proposed by Edsger Dijkstra (In a chapter of his book A Discipline of Programming Prentice-Hall, 1976). The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same color are together and their collective color groups are in the correct order.

var array = [3, 3, 2, 1, 3, 2, 1],
    MID = 2,
    i = 0,
    j = 0,
    n = array.length - 1;

while (j <= n) {
    if (array[j] < MID) {
        [array[i], array[j]] = [array[j], array[i]];
        i++;
        j++;
    } else if (array[j] > MID) {
        [array[n], array[j]] = [array[j], array[n]];
        n--;
    } else {
        j++;
    }
}

console.log(array);

Answer 2

Because of the fact that you know that the array can contain only 3 items, you can iterate over the entire array for each one of them, (this means that the algorithm runs 3*n times = O(3n) = O(n)).

The space restriction indicates that you need to work in-place, means, work on the input array.

This is my solution :]

function swap(i, j, arr) {
  const currentVal = arr[j];
  arr[j] = arr[i];
  arr[i] = currentVal;
}

function sort(arr) {
  let globalIndex = 0;
  [1, 2, 3].forEach(item => {
    for (let i = globalIndex; i < a.length; i++) {
      if (arr[i] === item) {
        swap(i, globalIndex, arr);
        globalIndex++;
      }
    }
  });
}

const a = [1, 2, 3, 2, 1, 1];

sort(a);

console.log(a);

Answer 3

You can count the number of occurrences of 1, 2, 3 and use that info to recreate/get the sorted array:

const arr = [3, 3, 2, 1, 3, 2, 1]

const count = arr.reduce((acc, curr) => {
  acc[curr]++;
  return acc;
}, {1: 0, 2: 0, 3: 0})

arr.forEach((_, j) => {
  if (j < count[1])
    arr[j] = 1
  else if (j < count[1] + count[2])
    arr[j] = 2
  else
    arr[j] = 3
})

console.log(arr)

Answer 4

According to me, you can simply initialize three variables as 0 for the counts of each 1, 2 and 3. Traverse the array once and increment the corresponding counter by 1 for values at every index i.e. if the value at a particular index is 2, increment the second variable by 1.

Once, you got the counts, (Count1 - 1)th index will be the last occurrence of 1, (Count1 + Count2 - 1)th index will be the last occurrence of 2 and (Count1 + Count2 + Count3 - 1)th index will be the last occurrence of 3.

You can traverse the whole array and assign the values accordingly. This way is somewhat like Counting Sort but is of course not stable. However, you have another option as already mentioned in previous answers -Dutch National Flag Problem

Answer 5

I followed a simple bruteforce approach which still gives O(n) at the end. After all O(2N) + O(3) = O(N)

import sys

def sortNums(nums):
    res = {}
    mi = sys.maxsize
    ma = -1 * sys.maxsize
    mid = 0
    for i in nums: #O(n)
        if i in res:
            res[i] += 1
        else:
            res[i] = 1
        if mi > i:
            mi = i
        if ma < i:
            ma = i
    
    for ele in res.keys(): #O(3)
        if ele != mi and ele != ma:
            mid = ele

    return ([mi] * res[mi]) + ( [mid] * res[mid] ) + ([ma] * res[ma]) # O(n)

print(sortNums([3, 3, 2, 1, 3, 2, 1]))
# [1, 1, 2, 2, 3, 3, 3]