Implementeren van QuickSort Sorteeralgoritme in Delphi

Een van de veel voorkomende problemen bij het programmeren is om een ​​reeks waarden in een bepaalde volgorde (oplopend of aflopend) te sorteren.

Hoewel er veel "standaard" sorteeralgoritmen zijn, is QuickSort een van de snelste. Quicksort sorteert door een verdeel en verover strategie om een ​​lijst in twee sublijsten te verdelen.

QuickSort-algoritme

Het basisconcept is om een ​​van de elementen in de array te kiezen, genaamd a spil. Rond het draaipunt worden andere elementen herschikt. Alles minder dan het draaipunt wordt links van het draaipunt verplaatst naar de linkerpartitie. Alles wat groter is dan de spil gaat in de juiste partitie. Op dit punt is elke partitie recursief "snel gesorteerd".

Hier is het QuickSort-algoritme geïmplementeerd in Delphi:

 procedure Snel sorteren(var EEN: reeks van Geheel getal; iLo, iHi: Integer);
var
  Lo, Hi, Pivot, T: geheel getal;
beginnen
  Lo: = iLo;
  Hallo: = iHi;
  Pivot: = A [(Lo + Hi) div 2];
  herhaling
    terwijl Een [Lo] < Pivot Doen Inc (Lo);
    terwijl A [Hi]> Pivot Doen Dec (Hallo);
    als zie <= Hi vervolgens
    beginnen
      T: = A [Lo];
      A [Lo]: = A [Hi];
      A [Hallo]: = T;
      Inc (Lo);
      Dec (Hallo);
    einde;
  tot Lo> Hallo;
  als Hallo> iLo vervolgens QuickSort (A, iLo, Hi);
  als zie < iHi vervolgens QuickSort (A, Lo, iHi);
einde;

Gebruik:

 var
  intArray: reeks van geheel getal;
beginnen
  SetLength (intArray, 10);
  // Voeg waarden toe aan intArray
  intArray [0]: = 2007;
  ...
  intArray [9]: = 1973;
  //soort
  QuickSort (intArray, Low (intArray), High (intArray));

Opmerking: in de praktijk wordt de QuickSort erg langzaam wanneer de array die eraan is doorgegeven al bijna wordt gesorteerd.

Er is een demo-programma dat wordt meegeleverd met Delphi, genaamd "thrddemo" in de map "Threads" dat twee extra sorteeralgoritmen toont: Bubble sort en Selection Sort.