METODO DE ORDENAMIENTO QUICKSORT

METODO DE ORDENAMIENTO QUICKSORT

[pic 1]

Mediante este informe le daré a conocer sobre la búsqueda binaria, su programa y su prueba de escritorio

BUSQUEDA BINARIA

La búsqueda binaria al igual que otros algoritmos como el Quicksort utiliza la técnica divide y vencerás. Uno de los requisitos antes de ejecutar la búsqueda binaria, es que el conjunto de elementos debe de estar ordenado.

Con el siguiente programa explicare un poco sobre este método

PROGRAMA:

[pic 2]

ARREGLO:

Dato a buscar es el numero 20

0           1           2          3             4           5         6            7         8           9

PRUEBA DE ESCRITORIO

Mediante este informe le daré a conocer sobre el método de ordenamiento:

QUICKSORT

El QuickSort o también llamado método rápido, es un método de ordenamiento se podría decir que es un poco complejo quiero decir un poco difícil de entender, pero este método es uno de los mas eficientes al momento de querer lograr un ordenamiento eficaz.

Este método se basa en la técnica DIVIDE Y VENCERAS lo que este método hace es dividir el problema en subproblemas de menor tamaño y se resuelven por separado para luego ser unidos de nuevo una vez resueltos los subproblemas.

Una de las principales características de este método es la rapidez y también realiza menos operaciones ya que el método utilizado es de partición.

EXPLICACIÓN ABSTRACTA DEL FUNCIONAMIENTO DE QUICKSORT

• Se elige un elemento v de la lista L de elementos al que se le llama pivote.
• Se particiona la lista L en tres listas:

L1 - que contiene todos los elementos de L menos v que sean menores o iguales que v

L2 - que contiene a v

L3 - que contiene todos los elementos de L menos v que sean mayores o iguales que v

• Se aplica la recursión sobre L1 y L3
• Se unen todas las soluciones que darán forma final a la lista L finalmente ordenada. Como L1 y L3 están ya ordenados, lo único que tenemos que hacer es concatenar L1, L2 y L3

Aunque este algoritmo parece sencillo, hay que implementar los pasos 1 y 3 de forma que se favorezca la velocidad de ejecución del algoritmo.

ELIGIENDO EL PIVOTE

La velocidad de ejecución del algoritmo depende en gran medida de cómo se implementa este mecanismo, una mala implementación puede suponer que el algoritmo se ejecute a una velocidad mediocre o incluso pésima. La elección del pivote determina las particiones de la lista de datos, por lo tanto, se puede decir que esta es la parte más crítica de la implementación del algoritmo QuickSort. Es importante intentar que al seleccionar el pivote v las particiones L1 y L3 tengan un tamaño idéntico, dentro de lo posible.

Una buena estrategia para solucionar la selección del pivote ampliamente extendida es la conocida como "a tres bandas". En esta estrategia lo que se persigue es hacer una media con los valores de tres de los elementos de la lista. Por ejemplo, si nuestra lista es [ 8, 4, 9, 3, 5, 7, 1, 6, 2] la media sería       (8 + 2 + 5) / 3 = 5 lo que daría lugar a las siguientes particiones:

•        L1 = [ 8, 9, 7, 6]

•        L2 = [ 5]

•        L3 = [ 1, 2, 4, 3]

Esta estrategia no nos asegura que siempre nos dará la mejor selección del pivote, sino que estadísticamente, la elección del pivote sea buena.

Otra forma más fácil de explicar el método QuickSort es de la siguiente forma:

ANALISIS:

Se tiene un array de n elementos, tomamos un valor del array como pivote (usualmente el primero), separamos los elementos menores a este pivote a la izquierda y los mayores a la derecha, es decir, dividimos el array en 2 subarrays.

Con estos subarrays se repite el mismo proceso de forma recursiva hasta que estos tengan más de 1 elemento. Por lo tanto, la función Quicksort quedaría de la siguiente manera:

// Función recursiva para hacer el ordenamiento

void quicksort(int *array, int start, int end)

{

    int pivot;

    if (start < end) {

        pivot = divide(array, start, end);

        // Ordeno la lista de los menores

        quicksort(array, start, pivot - 1);

        // Ordeno la lista de los mayores

        quicksort(array, pivot + 1, end);

    }

}

La magia para resolver este problema está en la función dividir.

Empezamos creando o generando un array de n elementos, por ejemplo la función rand() de C++ para generar aleatorios del 1 al 15, el arreglo quedó así:

...