elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Introducción a la Factorización De Semiprimos (RSA)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  C++ - Problema con implementación del QuickSort.
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] 2 Ir Abajo Respuesta Imprimir
Autor Tema: C++ - Problema con implementación del QuickSort.  (Leído 4,116 veces)
xaps

Desconectado Desconectado

Mensajes: 157



Ver Perfil
C++ - Problema con implementación del QuickSort.
« en: 24 Marzo 2014, 21:00 pm »

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
  1. int splitArray(vector<int>&v, int l, int r)
  2. {
  3.  int pivot = r;
  4.  int leftInd = l;
  5.  while(leftInd < pivot)
  6.  {
  7.    if(v[leftInd] > v[pivot])
  8.    {
  9.      swap(v, leftInd, pivot-1);
  10.      swap(v, pivot-1, pivot);
  11.      if(pivot>0) --pivot;
  12.    }
  13.    else ++leftInd;
  14.  }
  15.  return pivot;
  16. }
  17.  
  18. void quickSort(vector<int>& v, int l, int r)
  19. {
  20.  if(r > l)
  21.  {
  22.    int pivot = splitArray(v, l, r);
  23.    quickSort(v, l, pivot);
  24.    quickSort(v, pivot+1, r);
  25.  }
  26. }
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
  1. void quickSort(vector<int>& v, int l, int r)
  2. {
  3.  if(r > l)
  4.  {
  5.    int pivot = splitArray(v, l, r);
  6.    quickSort(v, l, pivot-1);  //AQUÍ EL ERROR, NO LE RESTABA 1 A PIVOT
  7.    quickSort(v, pivot+1, r);
  8.  }
  9. }

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 Desconectado

Mensajes: 1.211



Ver Perfil
Re: C++ - Problema con implementación del QuickSort.
« Respuesta #1 en: 24 Marzo 2014, 21:51 pm »

Código
  1. quickSort(v, l, pivot-1);  //AQUÍ EL ERROR, NO LE RESTABA 1 A PIVOT
Error típico xD


En línea

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

Desconectado Desconectado

Mensajes: 157



Ver Perfil
Re: C++ - Problema con implementación del QuickSort.
« Respuesta #2 en: 25 Marzo 2014, 15:18 pm »

Código
  1. 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 Desconectado

Mensajes: 1.211



Ver Perfil
Re: C++ - Problema con implementación del QuickSort.
« Respuesta #3 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.
En línea

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

Desconectado Desconectado

Mensajes: 157



Ver Perfil
Re: C++ - Problema con implementación del QuickSort.
« Respuesta #4 en: 25 Marzo 2014, 16:54 pm »

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 Desconectado

Mensajes: 1.211



Ver Perfil
Re: C++ - Problema con implementación del QuickSort.
« Respuesta #5 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
En línea

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

Desconectado Desconectado

Mensajes: 254



Ver Perfil WWW
Re: C++ - Problema con implementación del QuickSort.
« Respuesta #6 en: 25 Marzo 2014, 19:15 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.
En línea

Saludos, Yoel.
P.D..-   Para mayores dudas, puedes enviarme un mensaje personal (M.P.)
SXF

Desconectado Desconectado

Mensajes: 189



Ver Perfil WWW
Re: C++ - Problema con implementación del QuickSort.
« Respuesta #7 en: 26 Marzo 2014, 01:46 am »

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 Desconectado

Mensajes: 157



Ver Perfil
Re: C++ - Problema con implementación del QuickSort.
« Respuesta #8 en: 26 Marzo 2014, 22:13 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.
En línea

"The programmers of tomorrow are the wizards of the future" - Gave Newel
amchacon


Desconectado Desconectado

Mensajes: 1.211



Ver Perfil
Re: C++ - Problema con implementación del QuickSort.
« Respuesta #9 en: 26 Marzo 2014, 22:19 pm »

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

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

Lo digo para asegurarte de que está bien inicializado.
En línea

Por favor, no me manden MP con dudas. Usen el foro, gracias.

¡Visita mi programa estrella!

Rar File Missing: Esteganografía en un Rar
Páginas: [1] 2 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Quicksort
Java
mapers 4 3,403 Último mensaje 20 Septiembre 2010, 07:16 am
por mapers
[API Facebook + Url Amigables] Problema para implementacion !
PHP
Diabliyo 0 2,868 Último mensaje 25 Agosto 2011, 23:45 pm
por Diabliyo
Problema con separar interfaz de implementación de una clase.
Programación C/C++
reethok 6 5,730 Último mensaje 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 1,845 Último mensaje 14 Septiembre 2013, 04:49 am
por erest0r
problema implementacion try... catch
Java
andrex.125 3 2,087 Último mensaje 25 Septiembre 2013, 17:21 pm
por 1mpuls0
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines