Esta es una pregunta de Codign Interview.. Como ordenar una lista de n números únicos(1,2,3) con tiempo O(n)... esto es lo principal y el plus es hacerlo de modo que el tamaño del arreglo sea siempre el mismo. Ejemplo:
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]));
Mi función de arriba no se puede decir que es exactamente un ordenar de una lista ni que es la solución al problema solo ordena este arreglo en O(n)...
Lo que hace esta otra funcion abajo es simple.. aumenta el tamaño del arreglo al doble por el caso que todos sus elementos son 2 y entonces lo que se hace en ella no funcionaria; Luego recorre hasta su longitud anterior(actual/2) para ir ordenando sus elementos.. si es encuentra 1 no hace nada, si encuentra un 2 lo pone en la longitud maxima anterior+1, incrementa la variable len y elimina el elemento... y si es 3 hace push(al final del arreglo) y elimina el elemento.. luego tienes espacios vacios vacios en el arreglo y no cumples con el plus del problema de hacrlo en espacio O(1) pero es un ordenar en 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]))