javascript – Sort a list of numbers in O (n) time

Question:

This is a question from Codign Interview .. How to order a list of n unique numbers (1,2,3) with time O (n) … this is the main thing and the plus is to do it so that the size of the array is always the same. Example:

Input:[3, 3, 2, 1, 3, 2, 1]; 
Output:[1, 1, 2, 2, 3, 3, 3];
function sortNums(arr) {
    let one = [], two = [], three = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] == 3) three.push(arr[i])
        else if (arr[i] == 1) one.push(arr[i])
        else two.push(arr[i])
    }
    return one.concat(two).concat(three)
}
console.log(sortNums([3, 3, 2, 1, 3, 2, 1]));

My above function cannot tell what is exactly a sort of a list nor that it is the solution to the problem just sort this array in O (n) …


What this other function does below is simple .. it increases the size of the array to double in the case that all its elements are 2 and then what is done in it would not work; Then it goes to its previous length (current / 2) to sort its elements … if it finds 1 it does nothing, if it finds a 2 it puts it at the previous maximum length + 1, increases the variable len and eliminates the element … . and if it is 3, push (at the end of the array) and remove the element .. then you have empty spaces in the array and you don't meet the plus of the problem of doing it in O space (1) but it is an order in 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,2]))

Answer:

It turns out that this problem is an adaptation to the Dutch National Problem … this is a solution.

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);

to understand it better …

It starts by going through the arrangement from position 0 and comparing the values ​​with the intermediate element (MID), which in this case has a value of 2 because it is an arrangement of numbers (1,2,3), if it is less, it is placed on the left and increasing the value of the index of ordered elements and if it is not greater it places it at the end of the arrangement and decreases the value of j, if it is equal to 2 it continues .. once the end of the arrangement is reached, it is traversed in reverse to the position from the index …

Scroll to Top