Metodos de ordenamiento

Métodos de Ordenamiento
✓ Quick Sort
✓ Shell
✓ Insercion Directa

QUICKSORT 

El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición, en el mundo de habla hispana.
Este método es una mejora sustancial del método de intercambio directoy recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.

La idea central de este algoritmo consiste en los siguiente:
Se toma un elemento x de una posición cualquiera del arreglo.
Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores oiguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.
Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.

Ejemplo:
A: 15,67,08,16,44,27,12,35
Se selecciona A[i] x=15

Primera pasada (DER-IZQ)
A[8] >= x 35 >= 15 No hay intercambio
A[7] >=x 12 >= 15 Si hay intercambio

A: 12,67,08,16,44,27,15,35

(IZQ-DER)
A[2] < = X 67 < = 15 Si hay intercambio

A:12,15,08,16,44,27,67,35

2da. Pasada (DER-IZQ)
A[6] >= x 27 >= 15 No hay intercambio
A[5] >= x 44 >= 15 No hay intercambio
A[4] >= x 16 >= 15 No hay intercambio
A[3] >= x 08 >= 15 Si hay intercambio

A: 12,08,15,16,44,27,67,35

Como el recorrido de izquierda a derechadebería iniciarse en la misma posición
donde se encuentra el elemento x, el proceso se termina ya que el elemento x, se
encuentra en la posición correcta.

A: 12, 08, 15, 16, 44, 27, 67, 35
1er 2do Conjunto
Conjunto
16, 44, 27, 67, 35
x16

(DER-IZQ)
A[8]>=x No hay intercambio
A[7]>=x No hay intercambio
A[6]>=x No hay intercambio
A[5]>=x No hay intercambio

A: 12, 08, 15, 16, 44, 27,67, 35
xß44

(DER-IZQ)
A[8]>= x Si hay intercambio

A: 12, 08, 15, 16, 35, 27, 67, 44

(IZQ-DER)
A[6] < = x No hay intercambio
A[7] < = x Si hay intercambio
12, 08, 15, 16, 35, 27, 44, 67
12, 08, 15, 16, 35, 27, 44, 67
35, 27, 44, 67
xß35

(DER-IZQ)
A[8] >= x No hay intercambio
A[7] >= x No hay intercambio
A[6] >= x Si hay intercambio
12, 08, 15, 16, 27, 35, 44, 67
12,08
xß12(DER-IZQ)
A[2]>=x Si hay intercambio

EL VECTOR ORDENADO:
08,12,15,16,27,35,44,67

ANALISIS DE EFICIENCIA DEL METODO DE QUICKSORT 

Diversos estudios realizados sobre el comportamiento del mismo demuestran que si se escoge en cada pasada el elemento que ocupa la posición central del conjunto de datos a analizar, el número de pasadas necesarias para ordenar es del orden de Log n.Respecto al número de comparaciones, si el tamaño del arreglo es una potencia de 2, en la primera pasada realizará (n-1) comparaciones, en la 2ª pasada realizará (n-1)/2 comparaciones, pero en 2 conjuntos diferentes, en la tercera pasada realizará (n-1)/4 comparaciones pero en 4 conjuntos diferentes y así sucesivamente. 

Por lo tanto: C = (n-1) + 2(n -1)/2 + 4(n - 1)/4 + ....... + (n - 1)(n - 1)/(n -1) 
Lo cual es lo mismo que: C= (n - 1) + (n- 1) + ....... + (n - 1)
 

SHELL 
El método de shell es una versión mejorada del método de inserción directa recibe ese nombre en honor a su autor Donald L. Shell quien lo propuso en 1959. 
Este método también se conoce con el nombre de inserción con incrementos decrecientes.

En el método de ordenación Shell propone que las comparaciones entreelementos se efectúen con saltos de mayor tamaño pero con incrementos se efectúen con saltos de mayor tamaño pero con incrementos decrecientes, así los elementos quedarán ordenados en el arreglo. 

Ejemplo:
Se desean ordenarse las siguientes clave del arreglo
A: 15, 67, 08, 16, 44, 27, 12, 35, 56, 21, 13, 28, 60, 36, 07, 10

Primera Pasada
Los elementos se dividen en 8 grupos:
A: 15,...