Método de Inserción

Contenido

Método de Inserción 3

Método de la Burbuja 4

Método de Selección 5

Método Shell 6

Método de Mezcla o Merge 7

Método Rápido o Quick Sort 8

Método del Montículo o Heap Sort 10

Método de Inserción

El método de inserción recorre una lista tomando el elemento actual e insertándolo donde toque entre los que ya ha recorrido. Su complejidad es de O(n^2) en el peor de los casos pero es adaptativo y cuando los elementos se encuentran casi ordenados se convierte en O(n). Además casi no consume memoria extra.

Se utiliza cuando el problema es pequeño y de hecho, se utiliza como caso base de otros métodos de ordenación basados en divide y vencerás, cuando los conjuntos en los que queda dividido el problema son pequeños.

for i = 2:n,

for (k = i; k > 1 and a[k] < a[k-1]; k--)

swap a[k,k-1]

→ invariant: a[1..i] is sorted

end

Método de la Burbuja

Este método se parece mucho al de inserción (mismas complejidades y adaptabilidad) pero es algo más complejo. Parte del hecho de que lo que lleva recorrido no sólo está ordenado sino que está en su posición final y no habrá que cambiarlo. Se llama de la burbuja porque los elementos flotan hasta su posición correcta como lo harían las burbujas de una bebida gaseosa.

Aquí la cosa consiste en recorrer la lista al revés tratando de encontrar el elemento más bajo y dejarlo al principio de la lista. Ahora que ya tenemos el más bajo colocado, nos vamos a por el segundo (que, si nos damos cuenta, es el mismo problema si ignoramos el primero) y así sucesivamente.

Para encontrar el más pequeño, el recorrido inverso toma un elemento y el siguiente. Como recorremos la lista al revés, se espera que dos elementos estén ordenados si se encuentran como actual=grande y siguiente=pequeño. Si es así, no se hace nada y el actual pasa a ser el pequeño. Si no es así y tenemos actual=pequeño y siguiente=grande, se les da la vuelta y se continúa. Así, el pequeño va flotando hasta el comienzo de la lista.

Esto nos lleva a un coste en O(n^2) pero cuando los elementos están casi ordenados, los cambios extra producidos durante los sucesivos recorridos habrá tendido a colocar en su sitio los elementos desordenados por lo que la complejidad se reduce a O(n) y por tanto, hablamos de un algoritmo adaptativo.

for i = 1:n,

swapped = false

for j = n:i+1,

if a[j] < a[j-1],

swap a[j,j-1]

swapped = true

→ invariant: a[1..i] in final position

break if not swapped

end

Método de Selección

El primo tonto de los métodos de ordenación. ¿En qué consiste? Bueno, se busca el menor entre todos y se coloca al principio, luego se hace lo mismo con el resto; y otra vez; y otra vez…

El método de selección es el caso general del de la burbuja. La principal diferencia es que el algoritmo por selección no es adaptativo. En su recorrido para seleccionar el más bajo, así como el de la burbuja al menos daba la vuelta a los pares desordenados; el algoritmo de seleccionar no hace nada y la complejidad siempre es O(n^2). Ahora bien (tenía que haber algo bueno) minimiza el número de cambios.

for i = 1:n,

k = i

for j = i+1:n, if a[j] < a[k], k = j

→ invariant: a[k] smallest of a[i..n]

swap a[i,k]

→ invariant: a[1..i] in final position

end

Método Shell

Este método es muy ingenioso, consiste en aplicar el método de inserción sobre sublistas de la lista original, comenzando por pocos elementos poco ordenados y terminando en muchos elementos pero casi ordenados.

Para seleccionar la sublista se cuenta cada h elementos donde h varía desde el número de elementos de la lista hasta 1. Por ejemplo, considera la secuencia [5, 7, 9, 12, 3, 6, 8, 4, 5, 6, 3, 15, 17]. Si h = 13, cuenta 13 elementos y tendrás la sublista [17]. Si h = 3, cuenta cada 3 elementos y la sublista será [9, 6,5, 15]. Ahora tomando h = 2, obtenemos [7, 12, 6, 4, 6, 15] y si h = 1 entonces la lista es la original.

La idea es utilizar el método de inserción para ordenar cada sublista. Cada paso dejará la lista original más ordenada y el último paso es una inserción normal y corriente con una lista casi ordenada (caso donde el algoritmo se comporta mejor).

h = 1

while h < n, h = 3*h + 1

while h > 0,

h = h / 3

for k = 1:h, insertion sort a[k:h:n]

→ invariant: each h-sub-array is sorted

end

Método de Mezcla o Merge

El método de mezcla es muy fácil de entender. Consiste en partir la lista en dos, ordenarla y mezclar las sublistas ordenadas de nuevo en una sola.

¿Cómo se ordena cada sublista? Como quieras.

Una forma es aplicando de nuevo el método de mezcla. Se vuelve a dividir hasta que las sublistas o sean vacías ([]) o sean de un sólo elemento ([42]). Entonces puedes decir que están (trivialmente) ordenadas. El método se convierte en recursivo porque aplica el mismo algoritmo a subproblemas

...