(* recherche des sqrt(n) plus grands d'un tableau en un temps linéaire *) (* Idées: 1°) on complète le tableau en lui adjoingnant son plus petit à répétition jusqu'à avoir une liste dont le cardinal soit un carré n=pxp 2°) on pense le tableau en matrice 3°) dans chaque colonne on trouve le plus grand et on le stocke en ligne 1 4°) on cherche le +petit ppl1 et le +grand pgl1 de la ligne 1 5°) on extrait le pgl1 de sa colonne pour le ranger dans le tableau des grands 6°) on remplace pgl1 par ppl1 7°) on jette le reste de la colonne de ppl1 8°) on recommence avec la matrice à (p-1) colonnes 9°) on recommence avec la matrice à (p-2) colonnes *) let max_tab t= let rang_max=ref 0 and k=ref (-1) and val_max=ref t.(0) and long=vect_length t in while (!k !val_max then (val_max:=t.(!k); rang_max:= !k) done; !rang_max ;; (* ci-dessous la version tableau de minetmaxqui renvoie les emplacements des plus petits et plus grands en un tems ~3n/2 *) let range n= let rec prefixe p q= if p=q then [q] else p::prefixe (p+1) q in vect_of_list(prefixe 0 n) ;; (* ci-dessous "ou" signifie "où se trouve (k)?" *) let placeminetmaxtab t= let mini=ref 44 and maxi=ref 44 in let long=vect_length t and demi=(vect_length t) /2 in let ou=(range long) in let swap p q= let mem=ou.(p) in (ou.(p)<- ou.(q);ou.(q)<-mem) in for k=0 to demi do if t.(ou.(k))>t.(ou.(long-1-k)) then swap k (long-1-k); done; mini:=ou.(0); for k=1 to demi+1 do if t.(ou.(k))< t.(!mini) then mini:=ou.(k); done; maxi:=ou.(long-1); for k=long-2 downto demi do if t.(ou.(k))> t.(!maxi) then maxi:=ou.(k); done; (!mini,!maxi) ;;