Comparación entre métodos para ordenar datos

September 26, 2011

Hola!

Habitualmente en el contexto de una macro suele darse la necesidad de ordenar datos.

Adjunto un archivo que -en su columna A- contiene 10000 números distintos generados aleatoriamente, y se presentan cuatro métodos de ordenamiento seleccionables mediante una Lista desplegable. Ellos son:

a) Ordenamiento por burbujeo (o su "primo-hermano": por selección).

Es el más conocido de los métodos pues es el más sencillo para programar. Como era de esperarse: es -también y con mucho- el más ineficiente.

Ordenamiento Shell.

La idea es reagrupar el conjunto total en muchos subgrupos pequeños y ordenarlos separadamente. Luego los subgrupos van creciendo de tamaño hasta llegar al conjunto total: es un muy buen método.

c) Ordenamiento Quicksort.

Es la "gran estrella" de los algoritmos de ordenamiento conocidos. Se basa en elegir un elemento del conjunto (llamado "pivot") y disponer los menores o iguales que el pivot: a su izquierda y los mayores o iguales: a su derecha. Luego se procede del mismo modo -y recurrentemente- con los subgrupos así determinados.

d) Ordenamiento "clásico" del Excel.

El "clásico": Datos --> Ordenar

Tras seleccionar alguno de los métodos mencionados y obtener el conjunto ordenado, se mostrarán los tiempos de procesamiento.

Las conclusiones de esta comparativa serán a gusto del lector.

Saludos, Cacho R.

ManagementMethods.rar

Gerson Pineda · September 26, 2011

Cacho

Que excelente compendio de macros! sin duda el clasico es el mejor, y tu que dices?

Saludos desde Honduras

September 26, 2011

Coincido: el método más comunmente conocido -hasta- tiene un nombre simpático como Burbuja ó imponente como Selección.

¿El resto?... ¡No cuentan!

(jajajaja)

September 27, 2011

mmmmm, a mí me suena a chino, pero de todas formas mis agradecimientos por el aporte (En el sitio correspondiente y públicos).

neverdelimon1 · September 27, 2011

Hola

Magnifico aporte, por mi parte el metodo Quicksort, resulta mas eficiente (despues del médoto de excel), y casi estoy 'seguro' que es el mismo que usa excel, desde luego tener un método como este ya en código nativo Vba que permita procesar todo en memoria resulta una gran ventaja.

mis felicitaciones al master Cacho R

saludos

September 27, 2011

... tener un método como este ya en código nativo Vba que permita procesar todo en memoria resulta una gran ventaja ...

Mis felicitaciones al Gran Descubridor de las verdaderas razones por la que se me ocurrió publicar este análisis.

¡En efecto!... Hay muy poco código VB en la web con el desarrollo completo de los métodos de ordenamiento Shell y Quicksort.

Saludos, asimismo, a los amigos Gerson y Killer (alias New Face).

Cacho R.

Antoni · September 27, 2011

Hola:

Ya está guardado en mi Macropedia. Se echan en falta aportes de este tipo.

Saludos.

September 29, 2011

Si te gustó ese aporte, Antonio, entonces pronto -en cuanto lo encuentre- (pues no me acuerdo donde lo publiqué) te mostraré otro aporte que -seguro- también te gustará.

En efecto: me lo has recordado tú, en uno de tus recientes aportes a esta sección del Foro, de modo que estamos sintonizando "la misma onda".

Saludos, Cacho R.

digitalboy · April 11, 2012

Hola a todos!

Primero que nada! agradecer a Cacho por su gran aporte, estos aportes valen mucho, por que estos son grandes algoritmos que la gran mayoría deberíamos de saber, por lo menos de su existencia.

En un libro lei... "Incluso a los estudiantes mas avanzados de programacion hay que revelarles las tres principales tareas: Ordenación, Búsqueda y Optimización"

Hace años había ocaciones en que empresas tardaban en ordenar información de archivos de texto en uno o mas dias... incluso hoy mismo... quien podria ordenar un listado de 3,000,000 de numeros en Excel usando la herramienta de ordenar? es por eso la importancia de estos grandes algoritmos!

Hace tiempo que vi este post... pero no me di el tiempo de analizarlo a profundidad! Tenia mucho trabajo... hace unos días retome mis estudios en C, aprovechando que me encuentro trabajando desde casa y tengo mayor tiempo libre para estudiar por mi cuenta. Así que estudie el tema de la ordenación, los métodos de ordenación que leí, fueron:

-Burbuja

-Selección

-Inserción

-Shell

-Quicksort

Por lo tanto no estoy de acuerdo en lo siguiente:

Hola!
Ordenamiento por burbujeo (o su "primo-hermano": por selección).

Es el más conocido de los métodos pues es el más sencillo para programar. Como era de esperarse: es -también y con mucho- el más ineficiente.

Se hace referencia a que la el método de la burbuja y selección son igual de ineficientes... y no es lo mismo llegar a la meta en 60 minutos, que hacerlo en 40! La ordenación de la burbuja y la ordenación por selección son dos cosas realmente distintas.

Mi libro dice que Quicksort es el mejor algoritmo de ordenación existente hasta el momento, se comporta de manera natural y es recursivo por naturaleza.

De echo la ordenación selección que implementaste... te fallo algo en el for por que realice la prueba ordenando los 10,000 numeros y se tardo 16 segundos, yo hice mi propia version, la cual ordena 20,000 numeros y se tarda 19 segundos.

neverdelimon1

...

sugiere que Quicksort se encuentra de forma nativa en Excel... la verdad tengo mis dudas... ejecute la macro de cacho copiando los numeros por debajo de los ya existentes (con el doble de numeros) y se tardo:

[TABLE=width: 210]

[TR]

[TD]QuickSort[/TD]

[TD] 0.45313[/TD]

[/TR]

[TR]

[TD]Excel Sort[/TD]

[TD] 0.23438[/TD]

[/TR]

[/TABLE]

El metodo nativo de Excel es dos veces mas rapido que el implementado por el compañero o que paso ahi?

Muero de ganas por hacer mi version de QuickSort y ver si soy capaz de mejorar el tiempo.... ahora que tenga tiempo, jajaja!

Aquí pongo mi aportación al tema... se trata de un macro que ordena un archivo de texto con 20,000 números desordenados y los escribe ordenados en uno nuevo haciendo uso del método de la burbuja, selección e inserción, ademas de motrar el tiempo requerido en segundos, numero de comparaciones, intercambios y asignaciones. Mas adelante espero poder subir ejemplos de la ordenación Shell y Quicksort, por que la verdad a un no los domino al 100, en especial la ordenación rápida.

Les comento de otras pruebas que he realizado...

En lenguje C asigne numeros aleatorios del 1-1000 a un array de 100,000 elementos, se tardo:

87 segundos con la burbuja

36 segundos con la seleccion

45 segundos con la insercion

Pero... en Python... oh Dios! hice lo mismo que en C... y para ordenar los números utilice el método de lista sort, y solo tardo:

0.109000 segundos

Sera posible implementar algo para poder superar a Python? la verdad no lo se... pero lo intentare en C, no concibo que Python sea mas rápido que C ya que C es compilado y Python interpretado. Ademas Python esta echo en C, jajaja. Lo intentare... haré mi versión de Quicksort en C y en lugar de utilizar indexado de array, tratare de de utilizar aritmética de punteros. Ademas de que también tengo en mente optimizar la ordenación de selección usando punteros y una pila... veamos si es cierta mi alocada idea de que es posible superar Quicksort.

Ya me extendi bastante! jajaja... mas adelante subiré explicaciones mas detalladas y ejemplos en C, VBA y Python en mi blog para compartirlo por aqui.

Saludos!

numeros.zip