¿Qué es ordenamiento?

Es la operación de arreglar los registros de una tabla en algún orden secuencial de acuerdo con un criterio de ordenamiento.
El ordenamiento se efectúa con base en el valor de algún campo en un registro. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los miembros del conjunto ordenado.

Ej. de ordenamientos:

• Un directorio telefónico
• Tablas de contenido
• Bibliotecas
• Diccionarios

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.

¿Cuándo conviene usar un método de ordenamiento?

Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.
Algunos métodos de ordenamiento son:

Ordenamiento burbuja

El ordenamiento burbuja hace múltiples pasadas a lo largo de una lista. Compara los ítems adyacentes e intercambia los que no están en orden. Cada pasada a lo largo de la lista ubica el siguiente valor más grande en su lugar apropiado. En esencia, cada ítem “burbujea” hasta el lugar al que pertenece.

Ordenamiento por inserción

El ordenamiento por inserción, aunque sigue siendo O(n2), funciona de una manera ligeramente diferente. Siempre mantiene una sublista ordenada en las posiciones inferiores de la lista. Cada ítem nuevo se “inserta” de vuelta en la sublista previa de manera que la sublista ordenada sea un ítem más largo.

Ordenamiento Quicksort

El ordenamiento rápido usa dividir y conquistar para obtener las mismas ventajas que el ordenamiento por mezcla, pero sin utilizar almacenamiento adicional. Sin embargo, es posible que la lista no se divida por la mitad. Cuando esto sucede, veremos que el desempeño disminuye.
Un ordenamiento rápido primero selecciona un valor, que se denomina el valor pivote. Aunque hay muchas formas diferentes de elegir el valor pivote, simplemente usaremos el primer ítem de la lista. El papel del valor pivote es ayudar a dividir la lista. La posición real a la que pertenece el valor pivote en la lista final ordenada, comúnmente denominado punto de división se utilizará para dividir la lista para las llamadas posteriores a la función de ordenamiento rápido.

Ordenamiento Binsort

El algoritmo por cubetas es también denominado bucket sort o bin sort. Este algoritmo corre en tiempo lineal [esto es O(n)], debido a que el algoritmo asume que la entrada consiste en elementos en un rango pequeño, esto es, divide la entrada en n subconjuntos uniformes (cubetas) para después distribuir cada uno de los elementos en dichos subconjuntos. Así para producir la salida es únicamente necesario ordenar los elementos dentro de la cubeta y posteriormente en base al orden de cada cubeta listar cada elemento.

Ordenamiento radix sort

El ordenamiento radix se empieza con el dígito menos significativo y se acomoda la lista de elementos en base en el dígito de esa posición, luego se cambia al siguiente dígito y se vuelve a acomodar la lista en base a ese dígito y así consecutivamente hasta hacerse con todos los dígitos.

Ordenamiento heap sort

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.

Ordenamiento merge sort

El ordenamiento por mezcla es un algoritmo recursivo que divide continuamente una lista por la mitad. Si la lista está vacía o tiene un solo ítem, se ordena por definición (el caso base). Si la lista tiene más de un ítem, dividimos la lista e invocamos recursivamente un ordenamiento por mezcla para ambas mitades. Una vez que las dos mitades están ordenadas, se realiza la operación fundamental, denominada mezcla. La mezcla es el proceso de tomar dos listas ordenadas más pequeñas y combinarlas en una sola lista nueva y ordenada.

Referencias