(* les tris de tableaux : quicksort pour les caractères*) let etale s= let long=String.length s in let tab=Array.make long "a" in for k=0 to long-1 do tab.(k) <- String.make 1 s.[k] done; tab;; let test=etale "le tri rapide est le meilleur";; let affiche t = for k=0 to (Array.length t-1) do print_string" "; print_string t.(k) done; print_newline() ;; (*échange les valeurs des termes a et b de t*) let swap t a b= let old=t.(a) in t.(a)<-t.(b);t.(b)<-old ;; (* le tri par quicksort *) (* séparation de la partie de tab allant de min à max, avec la valeur piv comme pivot. cette commande n'est invoquée que quand max>=min+2 la valeur renvoyée est l'endroit de rangement du pivot *) let separe tab min max = let piv=tab.(min) and g=ref (min+1) and d=ref max in while !g<(!d) (* tab de min+1 à g-1 a tous ses termes <= piv=tab.(min) tab de d+1 à max a tous ses termes >= piv *) do (* on cherche le premier de ceux qui ne devraient pas être à gauche *) while ((!g<=(!d)) & (tab.(!g) <= piv)) do g:=!g+1 done; (* on cherche le dernier de ceux qui ne devraient pas être à droite *) while ((!d>(!g)) & (tab.(!d) > piv)) do d:=!d-1 done; (*on échange les coupables *) if !g<(!d) then begin swap tab !g !d; d:=!d-1;g:=!g+1 end else if !g=(!d) then d:=!d-1 done; (* fin du while !g