Algoritmos de Ordenación Básica

...

El algoritmo ordenación rápida puede ser resumido en cuatro pasos básicos. Presentados en el contexto de ordenar un arreglo, los pasos son los siguientes.

- Si el tamaño del arreglo es cero o uno, entonces regresa el arreglo. Este es el caso base.

- Selecciona un elemento del arreglo para ser usado como el elemento pivote. Este es el paso de selección del pivote.

- Crea dos nuevos arreglos. Coloca todos los elementos del arreglo original que son menores que el elemento pivote en uno de estos subarreglos y todos los elementos que son más grandes que el elemento pivote en el otro subarreglo. Este es el paso de la partición.

- Regresa el arreglo que contiene el resultado del subarreglo ordenado rápidamente que incluye los elementos menores que el pivote, seguidos por el pivote, y luego por el resultado del subarreglo ordenado rápidamente que incluye los elementos mayores que el pivote. Este es el paso de división recursiva.

El siguiente ejemplo ilustra cómo estos cuatro pasos ordenan un conjunto de datos. Considera el arreglo presentado en la Figura 1.

[pic 4]Figura 1 Un arreglo desordenado

Como el arreglo en la Figura 1 contiene más de un elemento, el algoritmo ordenación rápida entra al paso dos y selecciona un elemento pivote. Existen muchas estrategias diferentes a seguir para seleccionar este elemento pivote. Una que es sencilla, involucra seleccionar el elemento del centro del arreglo como el elemento pivote. Este elemento contiene el valor 33. Después de seleccionar el elemento pivote, ordenación rápida particiona los elementos restantes en dos subarreglos. Un subarreglo contiene los elementos del arreglo particionado cuyos valores son menores que 33, el otro subarreglo contiene los elementos cuyos valores son mayores que 33. La Figura 2 ilustra este primer paso de selección del elemento pivote y partición del arreglo. En esta figura, un círculo denota el elemento pivote.

[pic 5]Figura 2 Selección del pivote y partición del arreglo

La primera partición crea dos arreglos más pequeños. Luego el algoritmo ordenación rápida recursivamente se llama a sí mismo sobre estos arreglos. Observa que ambos arreglos contienen dos o más elementos. Por lo tanto, el algoritmo selecciona elementos pivote para cada arreglo y particiona los elementos restantes en arreglos más pequeños. El resultado de esto se muestra en la Figura 3.

[pic 6]Figura 3 Partición de segundo nivel

El algoritmo ordenación rápida solamente requiere seleccionar elementos pivote y particionar subarreglos que contienen más de un elemento. En la Figura 3, podemos ver que después de dos particiones tenemos cuatro subarreglos. Estos arreglos aparecen en la fila inferior de la figura. Comenzando del lado izquierdo de la figura, el primer subarreglo contiene sólo un elemento (el valor 3). El segundo subarreglo contiene los elementos 12 y 21, y el tercer subarreglo contiene los elementos 52 y 53. El cuarto subarreglo contiene cero elementos. El signo de conjunto vacío (un círculo con una diagonal atravesada) denota que este subarreglo contiene cero elementos. El algoritmo ordenación rápida no requiere elegir un pivote y particionar el primer y el cuarto arreglo debido a que cada uno de ellos contiene menos de dos elementos. En este punto, estos dos subarreglos están ordenados. Debido a que el segundo y tercer arreglo cada uno contiene más de un elemento, existe la posibilidad de que no estén ordenados. Ordenación rápida debe seleccionar un pivote y particionar estos arreglos de manera recursiva. Esto se muestra en la Figura 4.

[pic 7]Figura 4 Después de la última partición necesaria

La naturaleza recursiva de ordenación rápida rompe el arreglo original en subarreglos cada vez más pequeños. El definir un pivote y particionar estos subarreglos eventualmente resulta en el ordenamiento del arreglo completo. La Figura 5 muestra la versión ordenada del arreglo original del ejemplo en curso.

[pic 8]Figura 5 El arreglo ordenado

Implantación

En el Listado 1 se muestra una implantación del algoritmo ordenación rápida. Esta implantación de ordenación rápida usa la estrategia básica de seleccionar como pivote el elemento de en medio. Este es un enfoque simple para implantar, pero puede provocar problemas de eficiencia cuando el algoritmo selecciona el elemento más pequeño o más grande como pivote. En estos casos, el desempeño del algoritmo se degrada debido a que el algoritmo puede solamente ordenar rápidamente de forma recursiva un subarreglo en lugar de dos.

1:

2:

3:

4:

5:

6:

7:

8:

9:

10:

11:

12:

13:

14:

15:

16:

17:

18:

19:

20:

21:

22:

23:

24:

25:

26:

27:

28:

29:

30:

31:

32:

33:

34:

35:

36:

37:

38:

39:

40:

41:

42:

43:

44:

45:

46:

47:

48:

49: