MÉTODOS DE ORDENAMIENTO
METODOS DE ORDENAMIENTO
Debido a que las estructuras de datos son utilizadas
para almacenar información, para poder recuperar esa
información de manera eficiente es deseable que aquella
esté ordenada. Existen varios métodos para ordenar las
diferentes estructuras de datos básicas.
En general los métodos de ordenamiento no son
utilizados con frecuencia, en algunos casos sólo una vez.
Hay métodos muy simples de implementar que son
útiles en los casos en dónde el número de elementos a
ordenar no es muy grande (ej, menos de 500 elementos).
Por otro lado hay métodos sofisticados, más difíciles de
implementar pero que son más eficientes en cuestión de
tiempo de ejecución.
Los métodos sencillos por lo general requieren de
aproximadamente n x n pasos para ordenar n
elementos.
Los métodos simples son: insertion sort (o por inserción
directa) selection sort, bubble sort, y shellsort, en dónde
el último es una extensón al insertion sort, siendo más
rápido. Los métodos más complejos son el quick-sort, el
heap sort, radix y address-calculation sort. El ordenar
un grupo de datos significa mover los datos o sus
referencias para que queden en una secuencia tal que
represente un orden, el cual puede ser numérico,
alfabético o incluso alfanumérico, ascendente o
descendente.
ORDENAMIENTO DE BURBUJA
La Ordenación 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.
ORDENAMIENTO SHELL
El ordenamiento Shell (Shell sort en inglés) es
un algoritmo de ordenamiento. El método se
denomina Shellen honor de su inventor Donald Shell. Su
implementación original, requiere O(n2) comparaciones
e intercambios en el peor caso. Un cambio menor
presentado en el libro de V. Pratt produce una
implementación con un rendimiento de O(n log2 n) en el
peor caso. Esto es mejor que las O(n2) comparaciones
requeridas por algoritmos simples pero peor que el
óptimo O(n log n). Aunque es fácil desarrollar un
sentido intuitivo de cómo funciona este algoritmo, es
muy difícil analizar su tiempo de ejecución.
El ordenamiento por inserción (insertion sort en inglés) es
una manera muy natural de ordenar para un ser humano, y
puede usarse fácilmente para ordenar un mazo de cartas
numeradas en forma arbitraria. Requiere O(n²) operaciones
para ordenar una lista de n elementos.
- Buscar el mínimo elemento de la lista
- Intercambiarlo con el primero
- Buscar el mínimo en el resto de la lista
- Intercambiarlo con el segundo
En esta oportunidad aremos le metodo
de
Debido a que las estructuras de datos son utilizadas
para almacenar información, para poder recuperar esa
información de manera eficiente es deseable que aquella
esté ordenada. Existen varios métodos para ordenar las
diferentes estructuras de datos básicas.
En general los métodos de ordenamiento no son
utilizados con frecuencia, en algunos casos sólo una vez.
Hay métodos muy simples de implementar que son
útiles en los casos en dónde el número de elementos a
ordenar no es muy grande (ej, menos de 500 elementos).
Por otro lado hay métodos sofisticados, más difíciles de
implementar pero que son más eficientes en cuestión de
tiempo de ejecución.
Los métodos sencillos por lo general requieren de
aproximadamente n x n pasos para ordenar n
elementos.
Los métodos simples son: insertion sort (o por inserción
directa) selection sort, bubble sort, y shellsort, en dónde
el último es una extensón al insertion sort, siendo más
rápido. Los métodos más complejos son el quick-sort, el
heap sort, radix y address-calculation sort. El ordenar
un grupo de datos significa mover los datos o sus
referencias para que queden en una secuencia tal que
represente un orden, el cual puede ser numérico,
alfabético o incluso alfanumérico, ascendente o
descendente.
ORDENAMIENTO DE BURBUJA
La Ordenación 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.
ORDENAMIENTO SHELL
El ordenamiento Shell (Shell sort en inglés) es
un algoritmo de ordenamiento. El método se
denomina Shellen honor de su inventor Donald Shell. Su
implementación original, requiere O(n2) comparaciones
e intercambios en el peor caso. Un cambio menor
presentado en el libro de V. Pratt produce una
implementación con un rendimiento de O(n log2 n) en el
peor caso. Esto es mejor que las O(n2) comparaciones
requeridas por algoritmos simples pero peor que el
óptimo O(n log n). Aunque es fácil desarrollar un
sentido intuitivo de cómo funciona este algoritmo, es
muy difícil analizar su tiempo de ejecución.
El ordenamiento por inserción (insertion sort en inglés) es
una manera muy natural de ordenar para un ser humano, y
puede usarse fácilmente para ordenar un mazo de cartas
numeradas en forma arbitraria. Requiere O(n²) operaciones
para ordenar una lista de n elementos.
· mm2 / m,
