Tri QuickSort (variantes)

Le fait d’utiliser le tri par sélection lorsqu’on arrive à des morceaux de tableaux petits réduit le nombre de comparaisons et de permutations d’élément par rapport à un QuickSort complet, mais n’implique pas forcemment un gain de rapidité. Faites des tests sur vos données pour choisir d’utiliser ou non le tri par sélection et choisir le seuil (typiquement entre 3 et 5). Ce choix est particulièrement intéressant lorsque les comparaisons entre les données du tableau sont longues (ex: chaines).

Exemple en Delphi (Pascal) :

AlxQuickSort.pas

type TDonnee=Integer; //type de donnée à traiter, à modifier selon l’utilisation.

procedure alxQuickSort(var T: array of TDonnee);
begin
 alxQuickSort_(T, Low(T), High(T));
end;

procedure alxQuickSort_(var T: array of TDonnee; debut, fin: Integer);
var petit, grand:Integer; moyen, temp:TDonnee;
begin
 repeat //cf plus bas....
  if (fin-debut)<=4 then //si le segment du tableau est trop petit, utilise SelectionSort
  begin //4 est la valeur de seuil la plus efficace en général.
        //Si les données sont trés similaires (ex: array[1..1000]of 1..9), 3 est plus efficace
   selectionSort_(T,debut,fin);
   petit:=fin; //pour sortir du repeat //exit;
  end
  else
  begin
   petit:=debut; //les pointeurs d’indice de gauche et de droite
   grand:=fin;
   moyen:=T[(debut+fin) div 2]; //élément du milieu comme pivot
   repeat
    while T[petit]<moyen do Inc(petit);
    while T[grand]>moyen do Dec(grand);
    if petit<=grand then //dès que 2 éléments se trouvent du mauvais côté
    begin               //du pivot, ils sont permuttés
     temp:=T[petit];  //permutte les éléments
     T[petit]:=T[grand];
     T[grand]:=temp;
     Inc(petit);
     Dec(grand);
    end;
    {else if petit = grand then //si on veut réduire le nombre de permutations
    begin //perte d’efficacité due aux tests fréquents petit = grand
     Inc(petit);
     Dec(grand);
    end;}
   until petit>grand;
   //dès que les indices petit et grand se rencontrent, chaque moitié est envoyée à QuickSort
   //ici, la 2ème moitié est traitée par le repeat pour éviter une récursive
   if grand>debut then alxQuickSort_(T, debut, grand);

   debut:=petit; //....le repeat..until.....
  end;
 until petit>=fin //.....remplace: if petit<fin then alxQuickSort_(T, petit, fin);
                  //supprime une récursive=gain mémoire
end;

procedure selectionSort_(var T: array of TDonnee; const debut, fin: Integer);
var petit, grand:Integer; temp:TDonnee;
begin
 for petit:=debut to Pred(fin) do
  for grand:=fin downto Succ(petit) do
   if T[petit]>T[grand] then
   begin
    temp:=T[petit];
    T[petit]:=T[grand];
    T[grand]:=temp;
   end;
end;

Retour

Licence Creative Commons : Paternité - Partage des Conditions Initiales à l’Identique 2.0 France, "BY-SA (FR)"