Implementación del algoritmo de clasificación QuickSort en Delphi

Uno de los problemas comunes en la programación es ordenar una matriz de valores en algún orden (ascendente o descendente).

Si bien hay muchos algoritmos de clasificación "estándar", QuickSort es uno de los más rápidos. Quicksort ordena utilizando un estrategia de divide y vencerás dividir una lista en dos sublistas.

Algoritmo de clasificación rápida

El concepto básico es elegir uno de los elementos en la matriz, llamado pivote. Alrededor del pivote, se reorganizarán otros elementos. Todo menos que el pivote se mueve hacia la izquierda del pivote, hacia la partición izquierda. Todo lo que es mayor que el pivote entra en la partición correcta. En este punto, cada partición es recursiva "ordenada rápidamente".

Aquí está el algoritmo QuickSort implementado en Delphi:

 procedimiento Ordenación rápida(var UN: gama de Entero; iLo, iHi: Entero);
var
  Lo, hola, pivote, T: entero;
empezar
  Lo: = iLo;
  Hola: = iHi;
  Pivote: = A [(Lo + Hi) div 2];
  repetir
    mientras A [Lo] < Pivot hacer Inc (Lo);
    mientras A [Hola]> Pivote hacer Dic (hola);
    Si Lo <= Hi luego
    empezar
      T: = A [Lo];
      A [Lo]: = A [Hola];
      A [Hola]: = T;
      Inc (Lo);
      Dic (hola);
    final;
  hasta Lo> hola;
  Si Hola, iLo luego QuickSort (A, iLo, Hola);
  Si Lo < iHi luego QuickSort (A, Lo, iHi);
final;

Uso:

 var
  IntArray: gama de entero;
empezar
  SetLength (intArray, 10);
  // Agregar valores a intArray
  intArray [0]: = 2007;
  ...
  intArray [9]: = 1973;
  //ordenar
  QuickSort (intArray, Low (intArray), High (intArray));

Nota: en la práctica, QuickSort se vuelve muy lento cuando la matriz que se le pasó ya está cerca de ser ordenada.

Hay un programa de demostración que se envía con Delphi, llamado "thrddemo" en la carpeta "Threads" que muestra dos algoritmos de clasificación adicionales: clasificación de burbujas y clasificación de selección.