Algoritmos de Ordenamiento

 

Son algoritmos que fueron realizados para ordenar un conjunto de datos. Los algoritmos varían según su facilidad de entendimiento, su eficiencia, cantidad de código necesario para implementarlos, complejidad, requisitos necesarios de los datos.

Algunos de estos algoritmos de ordenamiento son:

 

Ordenamiento por Selección.

 

 

El algoritmo de selección es un algoritmo de ordenamiento sencillo que consiste en:

• Buscas el elemento más pequeño de la lista.
• Lo intercambias con el elemento ubicado en la primera posición de la lista.
• Buscas el segundo elemento más pequeño de la lista.
• Lo intercambias con el elemento que ocupa la segunda posición en la lista.
• Repites este proceso hasta que hayas ordenado toda la lista

 

Ordenamiento por Inserción.

 

 

Para ordenar una lista con n elementos, la ordenación por inserción comienza con el segundo elemento.  Se compara este segundo elemento con el primero y se coloca antes del primero si no es mayor que el primer elemento y tras el primer elemento si es mayor que éste.  En este punto, los dos primeros elementos están en el orden correcto.  El tercer elemento se compara con el primero y si es mayor que él se compara con el segundo.  Se coloca en la posición correcta entre los tres primeros elementos.

Para simular esto en un programa necesitamos tener en cuenta algo: no podemos desplazar los elementos así como así o se perderá un elemento. Lo que hacemos es guardar una copia del elemento actual y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el elemento guardado en la posición del último elemento que se desplazó.

 

Merge Sort.

 

 

El merge sort divide la lista a ser ordenada en dos mitades iguales y las pone en arrays separadas. Cada array es ordenado recursivamente, y luego se juntan en el array final. Este algoritmo tiene un comportamiento de O(n log n).

• Primera parte: ¿Cómo intercalar dos listas ordenadas en una sola lista ordenada de forma eficiente?

• Segunda parte: divide y vencerás. Se separa la lista original en dos trozos mismo tamaño (salvo listas de longitud impar) que se ordenan recursivamente, una vez ordenados se fusionan obteniendo una lista ordenada. Como todo basado en divide y vencerás tiene un caso base y un caso recursivo.

* Caso base, cuando la lista tiene 1 ó 0 elementos (0 se da si se trata de una lista vacía). Se devuelve la lista tal cual está.

* Caso recursivo, cuando la longitud de la lista es de al menos 2 elementos. Se divide la lista en dos trozos del mismo tamaño que se ordenan recursivamente. Una vez ordenado cada trozo, se fusionan y se devuelve la lista resultante.

 

Quick Sort.

 

 

El algoritmo quick sort es un algoritmo que utiliza la técnica de «Divide y Vencerás», utiliza un pivote y ordena los elementos según él.

El algoritmo funciona de la siguiente forma:

• Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
• Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

• La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
• Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

 

Shell Sort.

 

 

Inventado en 1959, éste algoritmo es el más eficiente de los del tipo O(n2). Pero también es el más complicado de los algoritmos de este tipo.

Es una mejora del método de inserción directa, utilizado cuando el array tiene un gran número de elementos. En este método no se compara a cada elemento con el de su izquierda, como en el de inserción, sino con el que está a un cierto número de lugares (llamado salto) a su izquierda.

Shell Sort mejora al método de inserción comparando los elementos separados por una distancia de varias posiciones, esto permite que un elemento tome “pasos más grandes” hacia su posición esperada.  Se realizan varias pasadas sobre los datos con pasos cada vez menores.  El último paso del Shell Sort es plenamente un ordenamiento por inserción pero para entonces se garantiza que el arreglo esté prácticamente ordenado.