Quicksort

Quicksort es un algoritmo de divide y vencerás . primero divide una gran lista en dos pequeñas sub-listas: los elementos de baja y los elementos de alta. puede recursivamente ordenar las listas sub-.

Los pasos son los siguientes:

1. Elija un elemento, llamado pivote , de la lista.

2.Reordenar la lista para que todos los elementos con valores menores que el pivote venir antes de que el pivote, mientras que todos los elementos con valores mayores que el pivote de venir después de él (los mismos valores pueden ir en cualquier dirección).Después de esta división, el pivote está en su posición final. Esto se llama la operación de partición.

3.Recursiva ordenar la lista de sub-elementos de menor y de la sub-lista de mayores elementos.

Pseudocodigo:

function quicksort(array)
     var list less, greater
     if length(array) ≤ 1
         return array  // an array of zero or one elements is already sorted
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

Referencia:
medusa.unimet.edu.ve/programacion/bppr12/Clases/.../QuickSort.ppt