El algoritmo elegido

QUICKSORT

El ordenamiento rápido (Quicksort ) es un algoritmo creado por el científico británico en computación C.A.R. Hoare, basado en la técnica de divide y venceras, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

DESCRIPCION DEL ALGORITMO

El algoritmo trabaja de la siguiente forma:

1. Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

2. Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

3. La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

4. Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

5. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.

6. En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).

7. En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas. Pero principalmente depende del pivote, si por ejemplo el algoritmo implementado toma como pivote siempre el primer elemento del array, y el array que le pasamos está ordenado, siempre va a generar a su izquierda un array vacío, lo que es ineficiente.

Fig. 1 Representacion Grafica de como funciona el algoritmo Quicksort

A través de este enlace Ver QuickSort usted puede ver cómo funciona este algoritmo.

BUBBLE SORT

La Ordenación de burbuja (Bubble Sort) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo uno de los más sencillo de implementar.

Fig. 2 Ejemplo de como funciona Bubble Sort