Métodos de Ordenamiento Quicksort y Shell.

Método de ordenamiento Quicksort

El método de quicksort es un algoritmo que permite ordenar los elementos en un tiempo proporcional siendo así considerado entre los más rápidos y eficientes. Este método se basa en dividir un problema en subproblemas y luego agrupar las respuestas de estos subproblemas para obtener la solución al problema central Teniendo dos etapas:

• Tiene como su primera etapa hallar a su elemento pivote, una vez seleccionado se ha de buscar el sistema para situar en la sublista izquierda todos los elementos menores al pivote y en la sublista derecha todos los elementos mayores al pivote.

• La segunda etapa requiere mover todos los elementos menores al pivote a la izquierda y los elementos mayores al pivote a la derecha. Para ello recorre la lista de izquierda a derecha utilizando un índice “i” que se inicializara en la posición más baja buscando un elemento mayor al pivote. También se recorre la lista de derecha a izquierda buscando un elemento menor, para ello se utiliza el índice “j” teniendo los siguientes pasos:

Los pasos que sigue el algoritmo quicksort:

·        Seleccionar el elemento central de a (0: n-1) como pivote.

·        Dividir los elementos restantes en particiones izquierda y derecha.

·         Ordenar la partición izquierda utilizando quicksort recursivamente.

·        La solución es partición izquierda seguida por el pivote y a continuación partición derecha.

Representación gráfica

del Método Shell Sort.

Método de Ordenamiento Shell Sort

La ordenación Shell debe el nombre a su inventor, D. L. Shell. Se suele denominar también ordenación por inserción con incrementos decrecientes. Se considera que el método Shell es una mejora de los métodos de inserción directa. En el algoritmo de inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es el más pequeño hay que realizar muchas comparaciones antes de colocarlo en su lugar definitivo. El algoritmo de Shell modifica los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con ello se consigue que la ordenación sea más rápida. Generalmente se toma como salto inicial n/2 (siendo n el número de elementos), luego se reduce el salto a la mitad en cada repetición hasta que el salto es de tamaño 1. El Ejemplo 6.1 ordena una lista de elementos siguiendo paso a paso el método de Shell.

¿Cómo funciona?

Los pasos a seguir por el algoritmo para una lista de n elementos son:

 1. Dividir la lista original en n/2 grupos de dos, considerando un incremento o salto entre los elementos de n/2.

 2. Clarificar cada grupo por separado, comparando las parejas de elementos, y si no están ordenados, se intercambian. 178 Algoritmos y estructuras de datos

3. Se divide ahora la lista en la mitad de grupos (n/4), con un incremento o salto entre los elementos también mitad (n/4), y nuevamente se clasifica cada grupo por separado.

4. Así sucesivamente, se sigue dividiendo la lista en la mitad de grupos que en el recorrido anterior con un incremento o salto decreciente en la mitad que el salto anterior, y luego clasificando cada grupo por separado.

5. El algoritmo termina cuando se consigue que el tamaño del salto es 1.

Representación gráfica

del Método Shell Sort.