Algoritmos de ordenamiento

Algoritmos de Ordenamiento
• Ordenamiento por intercambio
▪ Método de la burbuja
▪ Ordenamiento rápido (QuickSort)
• Ordenamiento por selección y con árboles
▪ Algoritmo por selección directa
▪ Ordenamiento por árboles binarios
▪ Ordenamiento de grupo (HeapSort)
• Ordenamiento por inserción
▪ Inserción simple
▪Inserción binaria
▪ Método de Shell
▪ Ordenamiento por cálculo de dirección
• Algoritmos de enumeración
▪ Método de los contadores
• Ordenamiento por intercalación y de base
▪ Ordenamiento por intercalación
▪ Algoritmo de Cook- Kim
▪ Ordenamiento por base

❖ Introducción

Los procesos de ordenamiento tienen un importanteimpacto en nuestra vida diaria. Existen innumerables ejemplos de procesos donde el ordenamiento de los datos es casi imprescindible para lograr eficiencia. Un caso típico son los procesos de búsqueda, donde a veces es necesario ordenar la información para después realizar la búsqueda de manera más eficiente. Ejemplo: búsqueda en un directorio telefónico.

❖ Desarrollo

Veamos qué se entiende porconjunto ordenado.

Un archivo de tamaño n es una secuencia de elementos a1, a2,…an. A cada elemento o nodo le llamaremos registro.

Cada registro tiene asociado una llave k que generalmente es un subcampo del registro. Ejemplo: del registro estudiante, podríamos tener como llave su carnet de identidad.

Se dice que una estructura está ordenada con respecto a la llave si:
i < j => que kiprecede a kj.
Un ordenamiento se puede clasificar como interno si los registros que se están ordenando están en la memoria principal, o externo si alguno de los registros que se están ordenando está en la memoria auxiliar. Dirigiremos la atención hacia los ordenamientos internos.

Es posible que dos registros de un archivo tengan la misma llave. Una técnica de ordenamiento se llama estable sipara todos los registros i y j tales que ki sea igual a kj, si r[i] precede a r[j] en el archivo original, entonces r[i] también precede a r[j] en el archivo ordenado. Es decir, un ordenamiento estable mantiene los registros de igual llave en el mismo orden relativo que estaban antes del ordenamiento

Debido a la relación que existe entre el ordenamiento y la búsqueda lo primero que hay quepreguntarse ante cualquier aplicación es si necesita hacerse algún proceso de ordenamiento.

Habrá que determinar si conviene realizar el ordenamiento, determinando si es más fácil buscar el elemento que ordenar la información. O si por el contrario el trabajo de búsqueda puede representar más trabajo que un ordenamiento al inicio.

Después de determinar si es necesario ordenar, habrá que decidirqué método utilizar. No existe ningún método superior al otro, todo depende del problema a resolver y los resultados que se deseen obtener para el conjunto de datos que se tenga.

Existen numerosos métodos para ordenar, el programador debe conocerlos, saber las características, ventajas y desventajas considerando factores como: longitud de la lista y su grado de ordenamiento para escoger elapropiado. Debe tenerse en cuenta que si el archivo es pequeño los métodos para minimizar tiempo y espacio son en esos casos peores que los métodos más simples, que son generalmente los menos eficientes.

Los métodos de ordenamiento para memoria interna, se clasifican en:

• Lineales o no lineales: lineal es cuando no se considera en el tratamiento ningún otro orden que no sea el secuencial,es decir, consideramos que estamos en presencia de un alista lineal. No lineal considera que existe una estructura en los datos, por ejemplo: un árbol o trata los elementos que están a una determinada distancia. Son eficientes para listas grandes.
• Simples o combinados: los simples utilizan la misma técnica en la solución del problema y los combinados utilizan varias técnicas (varios...