Implementera QuickSort-sorteringsalgoritm i Delphi

Ett av de vanliga problemen med programmering är att sortera en mängd värden i någon ordning (stigande eller fallande).

Det finns många "standard" -sorteringsalgoritmer, men QuickSort är en av de snabbaste. Quicksort sorterar genom att använda en dela och erövra strategi att dela upp en lista i två underlistor.

QuickSort-algoritm

Det grundläggande konceptet är att välja ett av elementen i matrisen, kallad a svänga. Runt pivoten omorganiseras andra element. Allt mindre än pivot flyttas till vänster om pivoten - till den vänstra partitionen. Allt större än pivot går till rätt partition. Vid denna punkt är varje partition rekursiv "snabbt sorterat".

Här är QuickSort-algoritmen implementerad i Delphi:

 procedur Quick (var A: matris av Heltal; iLo, iHi: heltal);
var
  Lo, Hej, Pivot, T: Heltal;
Börja
  Lo: = iLo;
  Hej: = iHi;
  Pivot: = A [(Lo + Hej) div 2];
  upprepa
    medan A [Lo] < Pivot do Inc (Lo);
    medan A [Hej]> Pivot do Dec (hej);
    om Lo <= Hi sedan
    Börja
      T: = A [Lo];
      A [Lo]: = A [Hej];
      A [Hej]: = T;
      Inc (Lo);
      Dec (hej);
    slutet;
  fram tills Lo> Hej;
  om Hej> iLo sedan QuickSort (A, iLo, Hej);
  om Lo < iHi sedan QuickSort (A, Lo, iHi);
slutet;

Användande:

 var
  intArray: matris av heltal;
Börja
  SetLength (intArray, 10);
  // Lägg till värden i intArray
  intArray [0]: = 2007;
  ...
  intArray [9]: = 1973;
  //sortera
  QuickSort (intArray, Low (intArray), High (intArray));

Obs: i praktiken blir QuickSort mycket långsam när matrisen som skickas till den redan är nära att sorteras.

Det finns ett demoprogram som skickas med Delphi, kallat "thrddemo" i mappen "Trådar" som visar ytterligare två sorteringsalgoritmer: Bubble sortering och Selection Sort.