Ver Mensaje Individual
  #1  
Antiguo 01-07-2005
Avatar de Delphius
[Delphius] Delphius is offline
Miembro Premium
 
Registrado: jul 2004
Ubicación: Salta, Argentina
Posts: 5.582
Reputación: 25
Delphius Va camino a la fama
Post Metodos de Ordenamiento. QuickSort vs Burbuja Mejorado

Hola foristas, de nuevo yo... ahora no con dudas sino con un debate que yo he sostenido conmigo mismo (yo me entiendo ).
Hace un tiempo dejé un hilo con una duda sobre el rendimiento del TStringList. La duda ya fue resuelta, pero ahora me he puesto a pensar en los métodos de ordenamiento.
Recuerden aquellas clases de estructuras de datos y algoritmos...
La pregunta ¿Cuál es el mejor? siempre va y viene... aunque muchos digan: QuickSort. A mi entender para determinar cual es el mejor se tiene que tener en cuenta:
1. Los tiempos de ejecución
2. Estabilidad: el desempeño en el mejor, peor y promedio.
3. El tamaño de la lista, arreglo o lo que se desee ordenar.
4. Frecuencia e Importancia de uso. Por ejemplo, ¿Para qué usar QickSort en un sistema X si esta funcionalidad sólo se va ha usar escasamente?
5. Memoria
6. Comparaciones
7. Intercambios
8. Que se desea ordenar (esto puede ser obviado)

En el hilo anterior (Rendimiento TStringList) Lepe me recomendó que haga uso del QickSort y me quedé pensando en si debo usarlo o no. Por un lado tiene razón, pero por otro lado tal vez no valga la pena. Y se me ocurrió abrir este hilo para que a manera de debate (más que como duda) opinen al respecto... Se que mucho para discutir no hay.

Bueno, la cosa es que lo que se pretende es ordenar una playlist (se puede ordenar por: Artista, Tema, Duración, Género, Directorio, Album en forma Ascendente y Descendente) y yo actualmente hago empleo del método de Burbuja Mejorado.
Para responderme a mi mismo seguí los puntos anteriores. Para hacer un examen más sencillo hice el supuesto de que ningún factor es más importante que otro; todos tienen igual importancia en el análisis, por tanto poseen igual ponderación o peso sobre la decisión.
1. Tiempos de Ejecución:
Las pruebas demuestran que QucikSort es más rápido, obvio. PUNTAJE: QuickSort 1 - Burbuja Mejorado 0.
2. Estabilidad:
2.1 Mejor Caso: QickSort O(n * log n), Burbuja: O(n^2) (en burbuja no me acuerdo bien si es asi)
2.2 Peor Caso: QickSort O(n^2), Burbuja: O(n^2)
2.2 Promedio: QickSort O(n * log n), Burbuja: O(n/2^2)
Entonces en cuanto a Estabilidad podemos decir que el Burbuja es mucho mas estable ya que la diferencia entre el mejor y el peso caso no es demasiada. PUNTAJE: 1 - 1

3. Tamaño:
No hay mucho que decir, pero basta con decir que el QickSort es más conveniente a medida que se aumenta el tamaño. PUNTAJE: 2 - 1
4. Frecuencia/Importancia de Uso:
Para lo que está pensado (ordenar Playlist) cabe decir que no es muy frecuente. Generalmente un usuario ya deja la lista ordenada según sus gustos, y rara vez la ordenará de nuevo con otro criterio. Por tanto, para que malgastar QuickSort por algo que rara vez se usará, PUNTAJE: 2 - 2, esto está parejo...
5. Memoria:
Al ser QickSort un algoritmo recursivo, necesita un manejo de memoria que depende de la arquitectura del computador y esto hace que consuma más memoria que el Burbuja. PUNTAJE: 2 - 3.
6. Comparaciones:
Si bien las comparaciones (para decir si es major o menor: ascendente o descendente) son proporcionales al tamaño, QickSort demuestra que debe realizar menos comparaciones que el burbuja. PUNTAJE: 3 - 3.
7. Intercambios:
QuickSort tiene un punto debil, cuanto más grande sea la distribución de los elementos (es decir cuanto mas mezclados estén) mayor intercambios debe hacer. Si bien el burbuja también sufre de ello, el crecimiento de dichos intercambios es más notable en QickSort. PUNTAJE: 3 - 4

Entonces he llegado a que PARA EL USO EN MI SISTEMA me conviene hacer uso del Burbuja Mejorado. ¿Que opinan ustedes?¿Pondrían otros factores a tener en cuenta, o usarían otra ponderación para hacer estos "cálculos"?¿O pondrían en el "partido" otros algoritmos?

PD: No es por hacer spam pero para el que lo desea, aquí les dejo la versión 1.21 de la unidad UPlayList . Se han hecho algunos cambios menores.
Archivos Adjuntos
Tipo de Archivo: zip UPlayList_1_21.zip (7,3 KB, 438 visitas)
__________________
Delphius
[Guia de estilo][Buscar]
Responder Con Cita