9

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

8
  • 2
    Disculpa mi ignorancia pero que es O(n) ?
    – user128299
    Commented el 25 oct. 2019 a las 22:23
  • 2
    Es una forma de medir el crecimiento del tiempo de ejecucion de una funcion.. es la solucion mas eficiente en tiempo
    – RazerJs
    Commented el 25 oct. 2019 a las 22:29
  • 3
    Hola, no es posible hacer un ordenamiento en O(n), los algoritmos más rápidos que existen de ordenamiento tienen complejidad de O(n * log(n)) Commented el 25 oct. 2019 a las 22:45
  • @DanielRodríguezMeza tienes bastante razon.. pero en este caso estoy casi seguro que se puede pq es una pregunta de coding interview y tiene el caso especial que son numeros y solo del 1 al 3
    – RazerJs
    Commented el 26 oct. 2019 a las 7:32
  • Hola, no se si sea posible, y si el hecho de que solo tenga 3 números con un tamaño constante lo haga diferente, tu código esta bien implementado pero si mal no estoy el concatenar también consume tiempo O(n), lo que menos consume tiempo seria el hecho de no usar listas sino mas bien implementarlo como si no existieran para que lo tengas en cuenta, y por último si logras alguna solución seria grato si la públicas!
    – DDR
    Commented el 27 oct. 2019 a las 14:53

5 respuestas 5

4

Resulto ser que este problema es una adaptacion al Dutch National Problem .. esta es una solucion.

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

para entenderlo mejor...

Se inicia recorriendo el arreglo desde la posicion 0 y comparando los valores con el elemento intermedio(MID) que en este caso tiene valor 2 por ser un arreglo de numeros(1,2,3) si es menor lo va colocando a la izquierda y aumentando el valor del indice de elementos ordenados y si no es mayor lo coloca al final del arreglo y disminuye el valor de j, si es igual a 2 continua.. una vez se llega al final del arreglo se recorre a la inversa hasta la posicion del indice...

2
  • Creo que mi segunda solución es equivalente a este algoritmo, ordenando a un lado u a otro y dejando el dos en medio. Commented el 29 oct. 2019 a las 18:21
  • si @PabloLozano el principio es el mismo y es casi igual... al final encontrastes la solcion :) ... la única parte diferente y se complica un poco es para el caso que el elemento sea igual a 3... te ganas la respuesta por la dedicacion... solo añadirle el en.wikipedia.org/wiki/Dutch_national_flag_problem
    – RazerJs
    Commented el 29 oct. 2019 a las 22:27
3

He encontrado una solución con una única pasada: recorro el array y si encuentro un 1 lo pongo en un lado (el inicio del array), si encuentro un tres lo pongo en en el otro extremo (al final). Cuando he terminado los 2 están todos en medio:

const log= console.log;
function sort(array) {
  let index1 = 0;
  let index3 = array.length - 1;
  
  for (let i = 0; i <= index3; i++) {
    if (array[i] === 3) {
      
      if (i < index3) {
        while(array[index3] ===3 && index3 > i) {
          index3--; //cada paso de este bucle, reduce en un paso el for
        }
        log('moviendo 3 a', index3);
        let aux = array[index3];
        array[index3] = array[i];
        array[i] = aux;
      }
      index3--;
    }
    if (array[i] === 1) {
      
      if (i > index1) {
        log('moviendo 1 a', index1);
        let aux = array[index1];
        array[index1] = array[i];
        array[i] = aux;
      }
      index1++;
    }
  }
  return array;
}

log(sort([1,2,3,1,2, 3,1,2,3,2, 2,2,3,3,3, 1,1]).toString());
log(sort([1,3,1,3,3,3,1,1,3,3,3,1]).toString());
log(sort([1,1,3,2,1, 3,1,1,3,1, 1,1,1,1,1, 1,1]).toString());
log(sort([2,3,3,3,3,3,3,3,3,3, 3,3,3,3,3, 3,1]).toString())

3

Investigando encontre esta funcion es una solucion en O(n) para listas de numeros; es el algoritmo de ordenamiento Radix... no es la solución correcta para esta pregunta.. lo que hace es parecido a mi primera función iniciando por los dígitos menos significativos los agrega a la una pila de cada digito y los regresa ordenados.. asi repite la cantidad segun la cantidad de digitos significativos del mayor numero.. abajo esta una imagen como mas claro lo entendi... la pila de los digitos del 0-9 y arriba como va quedando el arreglo luego de cada iteracion.. introducir la descripción de la imagen aquí

var getDigit = function (num, nth) {
    var ret = 0;
    while (nth--) {
        ret = num % 10
        num = Math.floor((num - ret) / 10)
    }
    return ret
}

// radixSort
function radixSort(list) {
    var max = Math.floor(Math.log10(Math.max(...list))),
        // obtener la longitud del mayor numero del arreglo
        digitBuckets = [],
        idx = 0;

    for (var i = 0; i < max + 1; i++) {
        // creando las listas de digitos
        digitBuckets = []
        for (var j = 0; j < list.length; j++) {
            var digit = getDigit(list[j], i + 1);

            digitBuckets[digit] = digitBuckets[digit] || [];
            digitBuckets[digit].push(list[j]);
        }

        // ordenando las listas de acuerdo a los digitos
        idx = 0
        for (var t = 0; t < digitBuckets.length; t++) {
            if (digitBuckets[t] && digitBuckets[t].length > 0) {
                for (j = 0; j < digitBuckets[t].length; j++) {
                    list[idx++] = digitBuckets[t][j];
                }
            }

        }
    }
    return list
}

console.log(radixSort([3, 3, 2, 1, 3, 2, 3, 1, 2, 1]));

2
  • En realidad Radix opera en O(kn)
    – Marcos
    Commented el 29 oct. 2019 a las 12:56
  • @Marcos si opera en O(k+n) lo que lo hace O(n)... no O(kn)
    – RazerJs
    Commented el 29 oct. 2019 a las 14:03
2

Existen algoritmos de ordenamiento definidos, los más usados son MergeSort y QuickSort con un O(N log N), que para ordenamiento de datos es un estándar, existen otras formas de ordenar como por ejemplo Radix Sort que si tiene una complejidad lineal O(N).

A su vez lenguajes como JavaScript incluyen métodos internos para hacer el ordenamiento.

Puedes usar arr.sort() que tiene una complejidad O(N log N) en la mayoría de casos:

//Input:[3, 3, 2, 1, 3, 2, 1]; 
//Output:[1, 1, 2, 2, 3, 3, 3];

const arr = [3, 3, 2, 1, 3, 2, 1];
const sortedArr = arr.sort((a, b) => a - b);

console.log(sortedArr); // [1, 1, 2, 2, 3, 3, 3]

1
  • gracias por responder... la solucion al problema no es la que busco pero has aportado algo que no sabia que es el algoritmo Radix que funciona O(n) para numeros de 1 cifra... tratare de inplementarlo. Saludos
    – RazerJs
    Commented el 26 oct. 2019 a las 7:41
1

Esta solución es de orden N, porque hace siempre 2 iteraciones (recorre menos de 2*N elementos): Recorre buscando los 1 y los pone al inicio, luego recorre buscando los 2... y los 3 ya estarán colocados

function sort(array) {
  let index=0;
  for (let v=1; v<3; v++) {
    
    for (let i=index; i<array.length; i++) {
      if (array[i] === v) {
        let aux = array[index];
        array[index] = array [i];
        array[i]=aux;
        index++;
      }
    }
  }
  return array;
}

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

Se puede generalizar para E elementos distintos, y tendrá siempre una complejidad de N*E:

function sort(array, values) {
  let index = 0;
  for (let v = 0; v < values.length - 1; v++) {
    let value = values[v];
    for (let i = index; i < array.length; i++) {
      if (array[i] === value) {
        let aux = array[index];
        array[index] = array [i];
        array[i]=aux;
        index++;
      }
    }
  }
  return array;
}

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

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

3
  • Esta solución no es de O(n), es de O(n*m), siendo m el número de elementos diferentes del array y n el nº de elementos del array. No es un mal algoritmo, ya que si no hay muchos valores diferentes se puede acercar a O(n). No existen algoritmos de ordenación de O(n).
    – chikebox
    Commented el 29 oct. 2019 a las 12:21
  • @chikebox estamos asumiendo que M es conocido y vale 3, por tanto es O(2n), que pertenece a O(n). Si trabajamos sólo con arrays con 3 elementos, siempre se cumple esta condición. Lo de generalizarlo era para mostrar que se basa en un algoritmo O(n^2) (el de la burbuja), pero que al restringir los valores podemos transformarlo en un O(n). No existen algoritmos generales de ordenación O(n), pero si sabemos que los datos son limitados, se pueden encontrar algoritmos restringidos a esos datos más eficientes Commented el 29 oct. 2019 a las 12:34
  • @chikebox si que existen para este caso especial revisa la respuesta abajo.. saludos
    – RazerJs
    Commented el 29 oct. 2019 a las 14:04

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.