Introducción

Divide y Venceras

Divide y vencerás es una técnica para diseñar algoritmos que consiste en descomponer el caso que haya que resolver en un cierto número de subcasos más pequeños del mismo problema.

Método de Ordenación Rápida (QuickSort)

El Algoritmo inventado por Hoare, que suele conocerse con el nombre de QuickSort u ordenación rápida, esta basado en el principio de Divide y Venceras.

  1. Se selecciona un pivote en particular de la lista. El valor óptimo sería aquél que esté precisamente en medio del rango de valores. Esto se hace para evitar el peor caso de Quicksort, que es seleccionar una llave del extremo. No obstante, incluso en el peor de los casos Quicksort funciona correctamente.
  2. Se divide la lista en dos partes, una con todos los elementos menores o iguales que el pivote seleccionado y otra con todos los elementos mayores o iguales.
  3. Se repiten los puntos 1 y 2 para cada parte restante hasta que la lista esté ordenada

 

                                       *ejemplo de como se ordenan los valores

 

Animacion de Quicksort: click aqui

 

Animación del Método QuickSort