Recursión infinita en quicksort de JavaScript?

algorithm sorting

Question

Aquí está el código de quicksort que escribí. La función no funciona porque no puede alcanzar el caso base. Si registro el pivote, r y l en la consola, siguen siendo los mismos sin importar cuántas veces se llame a la función de clasificación. Entonces me pregunto si el argumento l , r realmente no se pasa a la función como datos. ¿Por qué sucedió?

function sort(data){
    if(data.length < 2){
        return data;
    }
    else{
        var l = [];
        var r = [];
        var pivot = parseInt(data.length/2);
        for(i=0; i<data.length; i++){
            if(data[i] > data[pivot]){
                r.push(data[i]);
            }
            else{
                l.push(data[i]);
            }
        }
        return sort(l).concat(sort(r));
    }
}

Answer 1

Creo que el problema aquí es que su paso de partición no necesariamente reduce el conjunto de entrada. Por ejemplo, tracemos qué pasa si intenta ordenar [1, 2]. En este caso, su elemento pivote será el elemento 2. Como 1> 2 es falso, 1 se agrega a la lista l . Como 2> 2 es falso, 2 se agrega a la lista l . Como resultado, su llamada recursiva en la lista tendré exactamente los mismos argumentos que su llamada original, causando recursión infinita.

Para solucionar esto, intente dividir la entrada en tres listas: una de valores más pequeños, uno de valores iguales y uno de valores mayores. Este código se muestra aquí:

function sort(data){
  if (data.length < 2){
    return data;
  } else {
    var l = [];
    var r = [];
    var e = [];
    var i = 0;
    var pivot = (data.length / 2) | 0;

    for(i = 0; i < data.length; i++) {
      if (data[i] > data[pivot]) {
        r.push(data[i]);
      } else if (data[i] < data[pivot]) {
        l.push(data[i]);
      } else {
        e.push(data[i]);
      }
    }  
    return sort(l).concat(e, sort(r)); 
  }
}

Esta nueva versión agrupa explícitamente los elementos iguales en su propia lista, por lo que no son ordenados recursivamente por ninguna de las llamadas recursivas. También maneja con gracia los elementos duplicados.

¡Espero que esto ayude!

Answer 2

JavaScript pasa objetos por referencia (las matrices también son objetos). Si desea pasarlos por valor, debe usar la función de empalme como se explica here .

Tenga en cuenta que esto creará muchas copias de sus datos. Probablemente desee utilizar la función native sort ().

Answer 3

Si elige el valor más grande de la matriz como elemento pivote, todos los valores de data terminarán en la matriz l y ninguno en r . Por lo tanto, la recursión nunca se detendrá (y mantendrá l , r y pivot en los mismos valores). A menos que sea un ejercicio cerebral, el uso de data.sort() debería hacer un mejor trabajo. ;)