Algoritmos de Ordenamiento

Los algoritmos de ordenamientos sirven para ordenar vectores, listas u otras entidades donde hayan datos agrupados. A continuación veremos algunos de los algoritmo más comunes para ordenamiento de datos.

Bubble Sort (Ordenamiento de Burbuja)

Este algoritmo compara un elemento con el siguiente y si el siguiente es menos entonces intercambian posición. Estas comparaciones parten desde el primer elemento hasta el último. Al llegar al último elemeno si aun no se han ordenado vuelve a realizar otra pasada desde el primer elemento, esto hasta que termine de ordenar todos los elementos.

Complejidad Temporal

• Mejor Caso: O(n^2)
• Peor Caso: O(n^2)
• Caso Promedio: O(n^2)

Ejemplos:

Quick Sort (Ordenamiento Rápido)

Primero se elige un elemento de la lista, el cual se llamara pivote. Lo que hace el algoritmo es agrupar a todos los menores que el pivote al lado izquierdo y a todos los mayores al lado derecho. Si hay elementos iguales al pivote pueden ganarse a la izquierda o a la derecha. Una vez terminado esto el pivote ya esta situado en el lugar correcto de la lista.

El siguiente paso es ordenar los elementos al lado derecho del pivote y los del lado izquierdo del pivote generando 2 sublistas. El proceso se repite para todas las sublistas que tengan mas de un elemento hasta que se termine de ordenar.

Complejidad Temporal

• Mejor Caso: O(n)
• Peor Caso: O(n^2)
• Caso Promedio: O(n^2)

Ejemplos:

Shell Sort (Ordenamiento Shell)

Este ordenamiento hace que el arreglo se divida en sub arreglos y comparando los primeros elementos de cada arreglo. Supongamos que el arreglo se divide en 2. el primer arrglo esta a la izquierda y el segundo a la derecha. Si el elemento del primer subarreglo es mas grande que el del segundo entonces se intercambian posiciones. Esto se repite hasta que se ordenen todos los elementos del arreglo.

Complejidad Temporal

• Mejor Caso: O(n log n)
• Peor Caso: Depende
• Caso Promedio: Depende

Ejemplos:

Merge Sort (Ordenamiento por mezcla)

Este ordenamiento primero divide el arreglo en sub arreglos y los sub arreglos también los vuelve a dividir si es que es posible para dejar arreglos de menor cantidad de elementos, luego los arreglos se ordenan y se mezclan de a 2 ordenando y mezclando a la vez cada elemento de los 2 vectores. Cuando se mezclen los últimos 2 arreglos estará ordenado el vector.

Complejidad Temporal

• Mejor Caso: O(n log n)
• Peor Caso: O(n log n)
• Caso Promedio: O(n log n)

Ejemplos:

Heap Sort (ordenamiento por montículos)

Este algoritmo crea un arbol binario donde los indices van desde arriba hacia abajo y de izquierda a derecha. Se va agregando de a un elemento al arbol binario. Si el elemento agregado es mayor al padre se intercambia de posición en el arbol quedando el hijo como padre y el padre como hijo. Esto se repite hasta q se complete el arbol binario. Una vez completado el arbol binario se toma el valor mayor, es decir la raiz del arbol y se coloca en la ultima posicion del vector ordenado. Al sacar la raiz se debe volver a ordenar el arbol para tener el valor mayor del arbol (nueva raiz), para colocarlo en el vector ordenado. Esto se repite hasta que ya no quede ningun valor en el arbol.

Complejidad Temporal 

• Mejor Caso: O(n log n)
• Peor Caso: O(n log n)
• Caso Promedio: O(n log n)

Ejemplos:

Selection Sort (Ordenamiento por selección)

Este ordenamiento busca el elemento con menor valor de la lista y lo coloca en la primera posición del vector. Luego busca el siguiente elemento con menor valor y lo coloca en la segunda posición. Esto sigue sucesivamente hasta que se ordena completamente el vector desde la primera a la última posición.

Complejidad Temporal

• Mejor Caso: O(n^2)
• Peor Caso: O(n^2)
• Caso Promedio: O(n^2)

Ejemplos:

Insertion Sort (Ordenamiento por inserción)

Este ordenamiento selecciona un elemento y lo compara con el anterior. Si no hay un elemento anterior se toma el siguiente elemento. Si el elemento seleccionado es menor al anterior se intercambia de posicion y se sigue comparando hasta que llegue a compararse con el primer elemento. Despues se vuelve a la ultima posición que selecciono y selecciona el elemento siguiente para seguir comparando y realizar el mismo procedimiento. Esto se repite hasta q llegue a ordenar el elemento de la última posición.

Complejidad Temporal

• Mejor Caso: O(n)
• Peor Caso: O(n^2)
• Caso Promedio: O(n^2)

Ejemplos: