C++ - Problema con implementación del QuickSort.

Iniciado por xaps, 24 Marzo 2014, 21:00 PM

0 Miembros y 2 Visitantes están viendo este tema.

xaps

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:
Código (cpp) [Seleccionar]
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:
Código (cpp) [Seleccionar]
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
"The programmers of tomorrow are the wizards of the future" - Gave Newel

amchacon

Código (cpp) [Seleccionar]
quickSort(v, l, pivot-1);  //AQUÍ EL ERROR, NO LE RESTABA 1 A PIVOT
Error típico xD
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

xaps

Cita de: amchacon en 24 Marzo 2014, 21:51 PM
Código (cpp) [Seleccionar]
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?
"The programmers of tomorrow are the wizards of the future" - Gave Newel

amchacon

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.
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

xaps

Hombre, para llenar la pila con un QuickSort te han de meter un vector extremadamente grande... jajajaj
"The programmers of tomorrow are the wizards of the future" - Gave Newel

amchacon

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

Y L deberia tener como valor por defecto 0
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar

Yoel Alejandro

Cita de: amchacon en 25 Marzo 2014, 16:25 PM
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.

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.
Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)

SXF

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

xaps

Cita de: amchacon en 25 Marzo 2014, 18:19 PM
Por cierto R debería tener como valor por defecto v.size().

Y L deberia tener como valor por defecto 0
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.
"The programmers of tomorrow are the wizards of the future" - Gave Newel

amchacon

Me refiero:
Código (cpp) [Seleccionar]
void quickSort(vector<int>& v, int l = 0, int r = v.size()-1);

O bien usar un metodo lanzadera:
Código (cpp) [Seleccionar]
void quickSort(vector<int>& v)
{
    quickSort(v,0,v.size()-1);
}


Lo digo para asegurarte de que está bien inicializado.
Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar