Foro de elhacker.net

Buenas, estoy intentando implementar QuickSort para ordenar un vector cualquiera, pero estoy teniendo problemas.
La función ordena correctamente, pero una vez el vector está ordenado mi función recursiva sigue ejecutandose en un bucle infinito, y no logro encontrar el error.
El código del QuickSort es el siguiente:

int splitArray(vector<int>&v, int l, int r)
{
  int pivot = r;
  int leftInd = l;
  while(leftInd < pivot)
  {
    if(v[leftInd] > v[pivot])
    {
      swap(v, leftInd, pivot-1);
      swap(v, pivot-1, pivot);
      if(pivot>0) --pivot;
    }
    else ++leftInd;
  }
  return pivot;
}
 
void quickSort(vector<int>& v, int l, int r)
{
  if(r > l)
  {
    int pivot = splitArray(v, l, r);
    quickSort(v, l, pivot);
    quickSort(v, pivot+1, r);
  }
}

NOTA: las variables "l" y "r" significan "left" y "right". La función swap() es trivial, intercambia las dos variables que se le pasan por parametros (el primer parámetro es el vector, y los dos siguientes las posiciones de los valores a intercambiar).

Es muy probable que la implementación tampoco sea la más eficiente, ya que intenté entender un código de quicksort ya hecho y no lograba verlo, por lo que decidí implementarlo yo por mi cuenta. Acepto críticas y consejos :)

Muchas gracias.

Solucionado:

void quickSort(vector<int>& v, int l, int r)
{
  if(r > l)
  {
    int pivot = splitArray(v, l, r);
    quickSort(v, l, pivot-1);  //AQUÍ EL ERROR, NO LE RESTABA 1 A PIVOT
    quickSort(v, pivot+1, r);
  }
}

Saludos

quickSort(v, l, pivot-1);  //AQUÍ EL ERROR, NO LE RESTABA 1 A PIVOT

Error típico xD

Si, y estos son los peores D: Te puedes tirar horas mirando el código y no verlo... Por cierto, la implementación que te parece?

No me gusta hacer procesos asi recursivamente, cuesta mas tiempo y hay riesgo de que te estalle la pila.

Pero he de reconocer que recursivamente sale elegante.

Hombre, para llenar la pila con un QuickSort te han de meter un vector extremadamente grande... jajajaj

Por cierto R debería tener como valor por defecto v.size().

Y L deberia tener como valor por defecto 0

Estoy de acuerdo, la recursividad está bien para practicar y llegar a comprenderla, pero leí en un libro de programación que su uso excesivo se desaconseja. Aunque sea una solución "bonita", es menos eficiente que un ciclo repetitivo tradicional porque (1) corre el riesgo de desbordar la pila, y (2) incurre en sobrecarga de tiempo por llamadas a función.

Cuando llamas a función debes:

• colocar en la pila el estado actual de las variables del programa principal
• colocar en la pila la dirección retorno de la función (la siguiente instrucción a ser ejecutada luego de regresar de la misma)
• colocar en la pila los argumentos de llamada de la función
• cambiar la dirección del apuntador de programa a la primera instrucción ejecutable de la función que es llamada (esto es propiamente, invocar la función)
• ejecutar la función y al encontrar el return, colocar en la pila el valor de retorno de la misma
• rescatar de la pila la dirección de retorno al programa principal
• rescatar de la pila el estado de las variables del programa (no se bien si estos dos últimos pasos son así o al revés)

por eso es más costoso en tiempo de ejecución que un ciclo normal, lo que sería un problema solo en el caso de un excesivo número de repeticiones.

Es sólo un elemento más para tomar en cuenta, no es que yo esté prohibiendo el uso de la recursión, al final programador toma la decisión final de una manera ponderada.

Por cierto tiene pinta de ineficiente no??, esto se puede hacer de forma iterativa que es mucho mas rápido.

R tendría como valor v.size()-1 y L=0 en su primera llamada, la que se haría desde el "main". Os he adjuntado tan solo el código de lo que seria el algoritmo, si quereis que os pase el código completo comentadmelo y os lo subo a pastebin, pero no es nada del otro mundo: declarar el vector, leerlo, pasarle los parámetros tal como he indicado antes, y escribir el vector ordenado.

Sobre lo de usar un ciclo tradicional en vez de uno repetitivo estoy deacuerdo, pero me cuesta imaginarme ahora mismo como sería el código iterativo (debería pensarlo), supongo que sería algo más complicado y dificil de leer que el código recursivo. Como tu dices, tampoco le daría demasiada importancia a no ser que la entrada fuera exageradamente grande y la eficiencia fuera algo prioritario.

Me refiero:

void quickSort(vector<int>& v, int l = 0, int r = v.size()-1);

O bien usar un metodo lanzadera:

void quickSort(vector<int>& v)
{
    quickSort(v,0,v.size()-1);
}

Lo digo para asegurarte de que está bien inicializado.

Vale vale, ahora te entiendo jajaj
Normalmente uso lanzadera, ya que en la uni te miran mal cuando inicializas por defecto, pero esta bien recordarlo, gracias ^^