programacion







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 siignoramos 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 lavuelta 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 otravez…
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úmerode 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 terminandoen 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,...