Metodo La Sacudida

MÉTODO DE LA SACUDIDA

2.4 Clasificación por Vibración (Shaker Sort)

La idea básica de este algoritmo consiste en mezclar las dos formas en que se puede realizar el método de la burbuja.

En este algoritmo cada pasada tiene dos etapas.

En la primera etapa “de derecha a izquierda” se trasladan los elementos más pequeños hacia la parte izquierda del arreglo, almacenando en una variable la posición del último elemento intercambiado.

Las sucesivas pasadas trabajan con los componentes del arreglo comprendidos entre las posiciones almacenadas en las variables. El algoritmo de la variable que almacena el extremo izquierdo del arreglo es mayor que el contenido de la variable que almacena el extremo derecho.

Ejemplo:

Supongase que desea ordenarse las siguientes claves del arreglo A utilizando el método de la sacudida.

A: 15 67 08 44 27 12 35

PRIMERA PASADA

Primera etapa (de derecha a izquierda).

A[7]>A[8] (12>35) no hay intercambio

A[6]>A[7] (27>12) sí hay intercambio

A[5]>A[6] (44>12) sí hay intercambio

A[4]>A[5] (16>12) sí hay intercambio

A[3]>A[4] (08>12) no hay intercambio

A[2]>A[3] (67>08) sí hay intercambio

A[1]>A[2] (15>08) sí hay intercambio

Última posición de intercambio de derecha a izquierda : 2

Luego de la primera etapa de la primera pasada, el arreglo queda de la siguiente forma:

A: 08 15 67 12 16 44 27 35

Segunda etapa (de izquierda a derecha)

A[2]>A[3] (15>67) no hay intercambio

A[3]>A[4] (67>12) no hay intercambio

A[4]>A[5] (67>16) no hay intercambio

A[5]>A[6] (67>44) no hay intercambio

A[6]>A[7] (67>27) no hay intercambio

A[7]>A[8] (67>35) no hay intercambio

Última posición de intercambio de izquierda a derecha : 8

Luego de la segunda etapa de la primera pasada, el arreglo queda de la siguiente forma:

A: 08 15 12 16 27 35 67

SEGUNDA PASADA

A[6]>A[7] (27>35) no hay intercambio

A[5]>A[6] (44>27) sí hay intercambio

A[4]>A[5] (16>27) no hay intercambio

A[3]>A[4]

...