Tri rapide

[Gratteur]

Un algo pour trier rapidement un tableau (c'est le tri pivot réputé comme étant le plus rapide, prenant très peu de mémoire et très facile à adapter pour un tableau structuré) :

Code : Tout sélectionner

Procedure Partition(tab(1), debut, fin)
  Protected compteur = debut, pivot = tab(debut)
  For i=debut+1 To fin
    If tab(i) < pivot
      compteur+1
      Swap tab(compteur), tab(i)
    EndIf
  Next i
  Swap tab(compteur), tab(debut)
  ProcedureReturn compteur
EndProcedure

Procedure TriRapide(tab(1), debut, fin)
  Protected pivot
  If debut < fin
    pivot = Partition(tab(), debut, fin)
    TriRapide(tab(), debut, pivot-1)
    TriRapide(tab(), pivot+1, fin)
  EndIf
EndProcedure

Procedure Tri(tab(1))
  For k=0 To #nbelements/4
    Swap tab(k), tab(Random(#nbelements))
  Next k
  TriRapide(tab(), 0, #nbelements)
EndProcedure

A appeler avec :

Code : Tout sélectionner

Tri(tab()) ; avec tab = le nom de votre tableau