Answer about quicksort

Algoritmo QuickSort - Ordenamiento

2017-07-02 07:25:36

El ordenamiento rápido (quicksort en inglés) 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 vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

El algoritmo trabaja de la siguiente forma:

  • Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
  • Resituar los elementos de la lista de manera que a un lado queden todos los menores que él, y al otro los mayores.
  • 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.
  • 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.

  • Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
  • 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).
  • En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²).
  • En el caso promedio, el orden es O(n·log n).

  • ...

    Leer más