Club Delphi  
    FTP   CCD     Buscar   Trucos   Trabajo   Foros

Retroceder   Foros Club Delphi > Principal > Varios
Registrarse FAQ Miembros Calendario Guía de estilo Buscar Temas de Hoy Marcar Foros Como Leídos

Grupo de Teaming del ClubDelphi

 
 
Herramientas Buscar en Tema Desplegado
  #1  
Antiguo 01-07-2005
Avatar de Delphius
[Delphius] Delphius is offline
Miembro Premium
 
Registrado: jul 2004
Ubicación: Salta, Argentina
Posts: 5.582
Poder: 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
 


Herramientas Buscar en Tema
Buscar en Tema:

Búsqueda Avanzada
Desplegado

Normas de Publicación
no Puedes crear nuevos temas
no Puedes responder a temas
no Puedes adjuntar archivos
no Puedes editar tus mensajes

El código vB está habilitado
Las caritas están habilitado
Código [IMG] está habilitado
Código HTML está deshabilitado
Saltar a Foro


La franja horaria es GMT +2. Ahora son las 20:08:14.


Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Traducción al castellano por el equipo de moderadores del Club Delphi
Copyright 1996-2007 Club Delphi