Autor
|
Tema: C++ - Problema con implementación del QuickSort. (Leído 5,355 veces)
|
xaps
Desconectado
Mensajes: 157
|
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
|
|
« Última modificación: 24 Marzo 2014, 21:25 pm por xaps »
|
En línea
|
"The programmers of tomorrow are the wizards of the future" - Gave Newel
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
quickSort(v, l, pivot-1); //AQUÍ EL ERROR, NO LE RESTABA 1 A PIVOT
Error típico xD
|
|
|
En línea
|
|
|
|
xaps
Desconectado
Mensajes: 157
|
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?
|
|
|
En línea
|
"The programmers of tomorrow are the wizards of the future" - Gave Newel
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
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.
|
|
|
En línea
|
|
|
|
xaps
Desconectado
Mensajes: 157
|
Hombre, para llenar la pila con un QuickSort te han de meter un vector extremadamente grande... jajajaj
|
|
|
En línea
|
"The programmers of tomorrow are the wizards of the future" - Gave Newel
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
Por cierto R debería tener como valor por defecto v.size().
Y L deberia tener como valor por defecto 0
|
|
|
En línea
|
|
|
|
Yoel Alejandro
|
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.
|
|
|
En línea
|
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.
|
|
|
En línea
|
|
|
|
xaps
Desconectado
Mensajes: 157
|
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.
|
|
|
En línea
|
"The programmers of tomorrow are the wizards of the future" - Gave Newel
|
|
|
amchacon
Desconectado
Mensajes: 1.211
|
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.
|
|
|
En línea
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
Quicksort
Java
|
mapers
|
4
|
3,948
|
20 Septiembre 2010, 07:16 am
por mapers
|
|
|
[API Facebook + Url Amigables] Problema para implementacion !
PHP
|
Diabliyo
|
0
|
3,250
|
25 Agosto 2011, 23:45 pm
por Diabliyo
|
|
|
Problema con separar interfaz de implementación de una clase.
Programación C/C++
|
reethok
|
6
|
6,459
|
25 Diciembre 2011, 14:43 pm
por 3mp3z@ndo
|
|
|
Problema con ejercicio de separar interfaz de implementación de una clase
Programación C/C++
|
Mordecai
|
1
|
2,540
|
14 Septiembre 2013, 04:49 am
por erest0r
|
|
|
problema implementacion try... catch
Java
|
andrex.125
|
3
|
2,665
|
25 Septiembre 2013, 17:21 pm
por 1mpuls0
|
|