Metodo de busqueda rapida o Quicksort

ALGORITMO DE ORDENAMIENTO RAPIDO O QUICKSORT

Este algoritmo esta basado en la tecnica divide y vencerás (consiste en dividir el problema en pequeños subproblemas mas sencillos para luego estos ser resueltos con un calculo mas sencillo) asi crearemos arreglos mas pequeños para ordenar estos.
Los pasos que realiza este algoritmo son:

  1. Selecciona un valor del arreglo como pivote es decir un numero por el cual todos los elementos van a ser comparados.
  2. se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.
  3. luego se organizan los subarreglos que quedaron a mano derecha y izquierda.

Ejemplo:
Tenemos un arreglo que esta definido con los valores {22,40,4,10,12,35} los pasos en quicksort para arreglarlo son los siguientes:

  1. se toma como pivote el numero 22 recuerden puede ser cualquier numero.
  2. la búsqueda de izquierda a derecha encuentra el valor 40 que es mayor a pivote y la búsqueda de derecha a izquierda encuentra el valor 35 no lo toma porque es mayor a el numero pivote (recuerden que la búsqueda de derecha a izquierda busca los menores) entonces continua y encuentra a 12 que es menor que el pivote y se intercambian el resultado seria {21,12,4,10,40,35}
  3. si seguimos la búsqueda la primera encuentra el valor 40, y la segunda el valor 10,pero ya se han cruzado,así que paramos. Para terminar la división, se coloca el pivote en su lugar el numero encontrado por la segunda busqueda, el 10 quedando: {10,12,4,22,40,35}
  4. ahora tenemos dividido el arreglo en dos arreglos mas pequeños que son {10,12,4} y el {40,35}, y en ellos se repetirá el mismo proceso.

Acà les va el material multimedia :

Deja un comentario