LOS MÉTODOS DE ORDENAMIENTO SON:
-Merge Sort
-Heap Sort
-Quick Sort (Sort particionado)
-Shell Sort
-Bubble Sort
-archivo Inserción y Selección directa.
viernes, 20 de marzo de 2009
MERGE SORT
Este algoritmo tambien es llamado de intercanbio o combinacion, debido que combina (intercala) dos estructuras previamente ordenadas.
Este algoritmo consiste en:
- Dividir el grupo de datos en dos y ordenar por separado cada mitad.
- Cuando se tengan las mitades ordenadas, pueden irse mezclando para obtener fácilmente una secuencia ordenada.
El algoritmo MergeSort Utiliza los siguientes tres pasos:
DIVIDIR: divide la secuencia de "n" elementos a ordenar en dos subsecuencias de "n/2" elementos cada una.
VENCER: ordena las dos subsecuencias de manera recursiva mediante el algoritmo MERGESORT.
COMBINAR: combina las dos subsecuencias ordenadas para generar la solución.
De ahí su comparación con el paradigma algorítmico: "Divide y Vencerás".
Este algoritmo fue desarrollado por el matemático húngaro John Von Neumann en 1945.
[Thomas Cormen, 2001].
Este algoritmo consiste en:
- Dividir el grupo de datos en dos y ordenar por separado cada mitad.
- Cuando se tengan las mitades ordenadas, pueden irse mezclando para obtener fácilmente una secuencia ordenada.
El algoritmo MergeSort Utiliza los siguientes tres pasos:
DIVIDIR: divide la secuencia de "n" elementos a ordenar en dos subsecuencias de "n/2" elementos cada una.
VENCER: ordena las dos subsecuencias de manera recursiva mediante el algoritmo MERGESORT.
COMBINAR: combina las dos subsecuencias ordenadas para generar la solución.
De ahí su comparación con el paradigma algorítmico: "Divide y Vencerás".
Este algoritmo fue desarrollado por el matemático húngaro John Von Neumann en 1945.
[Thomas Cormen, 2001].
HEAP SORT
El ordenamiento por montículos (Heap sort en inglés) es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O(n log n).
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él.
QUICK SORT
Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). El algoritmo fundamental es el siguiente:
* Eliges un elemento de la lista. Puede ser cualquiera (en Optimizando veremos una forma más efectiva). Lo llamaremos elemento de división.
* Buscas la posición que le corresponde en la lista ordenada (explicado más abajo).
* Acomodas los elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él y al otro los mayores (explicado más abajo también). En este momento el elemento de división separa la lista en dos sublistas (de ahí su nombre).
* Realizas esto de forma recursiva para cada sublista mientras éstas tengan un largo mayor que 1. Una vez terminado este proceso todos los elementos estarán ordenados.
Una idea preliminar para ubicar el elemento de división en su posición final sería contar la cantidad de elementos menores y colocarlo un lugar más arriba. Pero luego habría que mover todos estos elementos a la izquierda del elemento, para que se cumpla la condición y pueda aplicarse la recursividad. Reflexionando un poco más se obtiene un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos contador por la izquierda, y j, al que llamaremos contador por la derecha. El algoritmo es éste:
* Recorres la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).
* Cuando lista[i] sea mayor que el elemento de división y lista[j] sea menor los intercambias.
* Repites esto hasta que se crucen los índices.
* El punto en que se cruzan los índices es la posición adecuada para colocar el elemento de división, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).
* Eliges un elemento de la lista. Puede ser cualquiera (en Optimizando veremos una forma más efectiva). Lo llamaremos elemento de división.
* Buscas la posición que le corresponde en la lista ordenada (explicado más abajo).
* Acomodas los elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él y al otro los mayores (explicado más abajo también). En este momento el elemento de división separa la lista en dos sublistas (de ahí su nombre).
* Realizas esto de forma recursiva para cada sublista mientras éstas tengan un largo mayor que 1. Una vez terminado este proceso todos los elementos estarán ordenados.
Una idea preliminar para ubicar el elemento de división en su posición final sería contar la cantidad de elementos menores y colocarlo un lugar más arriba. Pero luego habría que mover todos estos elementos a la izquierda del elemento, para que se cumpla la condición y pueda aplicarse la recursividad. Reflexionando un poco más se obtiene un procedimiento mucho más efectivo. Se utilizan dos índices: i, al que llamaremos contador por la izquierda, y j, al que llamaremos contador por la derecha. El algoritmo es éste:
* Recorres la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento), y por la derecha con j (desde el último elemento).
* Cuando lista[i] sea mayor que el elemento de división y lista[j] sea menor los intercambias.
* Repites esto hasta que se crucen los índices.
* El punto en que se cruzan los índices es la posición adecuada para colocar el elemento de división, porque sabemos que a un lado los elementos son todos menores y al otro son todos mayores (o habrían sido intercambiados).
SHELL SORT
Debe su nombre al ingeniero y matemático estadounidense Donald Shell , que lo publicó en la revista Communications of the ACM en 1959.
Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.
CARACTERISTICAS
-Se trata de un algoritmo de ordenación interna; los datos están en memoria principal. Podría utilizarse para ordenación externa (en memoria secundaria) siempre y cuando se disponga de acceso aleatorio, pero el algoritmo no fue ideado para eso.
-Se basa en comparaciones e intercambios.
-Necesita que el tiempo de acceso a cualquier dato sea constante (es decir, fue ideado para trabajar con arrays, arrays de referencias o punteros, etc...). Ojo a otras estructuras, como listas enlazadas, etc... ya que en ese caso, el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.
-El estudio de su complejidad no es trivial, sino todo lo contrario. La implementación original de Shell tiene una complejidad en el peor caso de O(n2), aunque en un caso promedio o en casos típicos comprobados empíricamente, los resultados son mucho mejores que con la burbuja, selección directa o inserción directa, cuya complejidad en el peor caso también es del orden de O(n2).
-En cierto modo, puede considerarse una ampliación del algoritmo de inserción directa, con lo cual, conviene tenerlo claro antes de meterse con el de Shell.
-No es un algoritmo en-línea.
Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.
CARACTERISTICAS
-Se trata de un algoritmo de ordenación interna; los datos están en memoria principal. Podría utilizarse para ordenación externa (en memoria secundaria) siempre y cuando se disponga de acceso aleatorio, pero el algoritmo no fue ideado para eso.
-Se basa en comparaciones e intercambios.
-Necesita que el tiempo de acceso a cualquier dato sea constante (es decir, fue ideado para trabajar con arrays, arrays de referencias o punteros, etc...). Ojo a otras estructuras, como listas enlazadas, etc... ya que en ese caso, el tiempo de acceso a un elemento no es constante, depende de la posición del elemento.
-El estudio de su complejidad no es trivial, sino todo lo contrario. La implementación original de Shell tiene una complejidad en el peor caso de O(n2), aunque en un caso promedio o en casos típicos comprobados empíricamente, los resultados son mucho mejores que con la burbuja, selección directa o inserción directa, cuya complejidad en el peor caso también es del orden de O(n2).
-En cierto modo, puede considerarse una ampliación del algoritmo de inserción directa, con lo cual, conviene tenerlo claro antes de meterse con el de Shell.
-No es un algoritmo en-línea.
BUBBLE SORT
El Ordenamiento de Burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo.
Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.
Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar.
INSERCION Y SELECCION DIRECTA
INSERCION DIRECTA
El algoritmo de ordenación por el método de inserción directa es un algoritmo relativamente sencillo y se comporta razonablemente bien en gran cantidad de situaciones.
Completa la tripleta de los algoritmos de ordenación más básicos y de orden de complejidad cuadrático, junto con SelectionSort y BubbleSort.
Se basa en intentar construir una lista ordenada en el interior del array a ordenar.
De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza una cantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene un par de características que lo hacen aventajar a los otros dos en la mayor parte de las situaciones.
SELECCIÓN DIRECTA
El algoritmo de ordenación por el método de selección directa es un algoritmo relativamente sencillo y uno de los más fáciles de recordar e implementar.
Se basa en realizar varias pasadas, intentando encontrar en cada una de ellas el elemento que según el criterio de ordenación es mínimo y colocándolo posteriormente en su sitio.
A efectos prácticos, no suele dar resultados buenos si se compara con otros métodos de ordenación. Realiza una enorme cantidad de comparaciones, pero en contrapartida, muy pocos intercambios. Eso hace que su utilización se restrinja en general a dos situaciones: o bien necesitamos un algoritmo sencillito para ordenar unos pocos datos y cogemos éste mismo que no está mal y es facil de recordar, o bien tenemos una situación en la cual escribir en el array es mucho más gravoso que leer, como puede ser un escenario en el que intervengan determinados dispositivos de almacenamiento o memorias tipo flash, eeprom, etc. para el soporte de los datos.
Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no. (ver Algoritmos de ordenación).
Read more: "Ordenación por selección directa (SelectionSort) - [La tecla de ESCAPE]" - http://latecladeescape.com/w0/con-nombre-propio/ordenacion-por-seleccion-directa-selectionsort.html#ixzz0AKnLzadF
Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no. (ver Algoritmos de ordenación).
Read more: "Ordenación por inserción directa (InsertionSort) - [La tecla de ESCAPE]" - http://latecladeescape.com/w0/con-nombre-propio/ordenacion-por-insercion-directa-insertionsort.html#ixzz0AKmKnPda
El algoritmo de ordenación por el método de inserción directa es un algoritmo relativamente sencillo y se comporta razonablemente bien en gran cantidad de situaciones.
Completa la tripleta de los algoritmos de ordenación más básicos y de orden de complejidad cuadrático, junto con SelectionSort y BubbleSort.
Se basa en intentar construir una lista ordenada en el interior del array a ordenar.
De estos tres algoritmos es el que mejor resultado da a efectos prácticos. Realiza una cantidad de comparaciones bastante equilibrada con respecto a los intercambios, y tiene un par de características que lo hacen aventajar a los otros dos en la mayor parte de las situaciones.
SELECCIÓN DIRECTA
El algoritmo de ordenación por el método de selección directa es un algoritmo relativamente sencillo y uno de los más fáciles de recordar e implementar.
Se basa en realizar varias pasadas, intentando encontrar en cada una de ellas el elemento que según el criterio de ordenación es mínimo y colocándolo posteriormente en su sitio.
A efectos prácticos, no suele dar resultados buenos si se compara con otros métodos de ordenación. Realiza una enorme cantidad de comparaciones, pero en contrapartida, muy pocos intercambios. Eso hace que su utilización se restrinja en general a dos situaciones: o bien necesitamos un algoritmo sencillito para ordenar unos pocos datos y cogemos éste mismo que no está mal y es facil de recordar, o bien tenemos una situación en la cual escribir en el array es mucho más gravoso que leer, como puede ser un escenario en el que intervengan determinados dispositivos de almacenamiento o memorias tipo flash, eeprom, etc. para el soporte de los datos.
Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no. (ver Algoritmos de ordenación).
Read more: "Ordenación por selección directa (SelectionSort) - [La tecla de ESCAPE]" - http://latecladeescape.com/w0/con-nombre-propio/ordenacion-por-seleccion-directa-selectionsort.html#ixzz0AKnLzadF
Este algoritmo se basa en hacer comparaciones, así que para que realice su trabajo de ordenación son imprescindibles dos cosas: un array o estructura similar de elementos comparables y un criterio claro de comparación, tal que dados dos elementos nos diga si están en orden o no. (ver Algoritmos de ordenación).
Read more: "Ordenación por inserción directa (InsertionSort) - [La tecla de ESCAPE]" - http://latecladeescape.com/w0/con-nombre-propio/ordenacion-por-insercion-directa-insertionsort.html#ixzz0AKmKnPda
Suscribirse a:
Entradas (Atom)
