#open "random";;init (int_of_float (sys__time()));;

(* Création d'un tableau aléatoire de p+1 entiers entre 1 et n *)
let alea p n= let tabini=make_vect p 0 in
	for k=0 to (p-1) do tabini.(k)<-(1+int n) done;
	tabini
;;

(* Tri par insertion d'une partie de tableau *)
let tri_partie tab deb fin =
	let swap a b=let temp=tab.(a) in (tab.(a)<-tab.(b); tab.(b)<-temp)
in	let insere k = let p=ref (k-1) and val=tab.(k) in
		while (!p>=deb && val<tab.(!p)) do (swap (!p+1) !p; decr p) done
in for k=deb to fin do insere k done;;

(* Recherche du min et du max d'un tableau *)
let min_max tab =
	let lg=vect_length tab -1 
	and maxi=ref tab.(0) and mini=ref tab.(0)
in for c=1 to lg do
		if tab.(c)> !maxi
		then maxi:=tab.(c)
		else	if tab.(c)< !mini
				then mini:= tab.(c)
	done;
	(!mini, !maxi)
;;

(* Voilà Flashsort : un tri linéaire ... TADA !!*)
let classement tab =
	let long=vect_length tab and (deb,fin)=min_max tab and tas=5
in	let rapport = 	let longf=float_of_int long and tasf=float_of_int tas
						and debf=float_of_int deb and finf=float_of_int fin
						in longf/.tasf/.(finf-.debf)
in let calc_classe x = let xf=float_of_int x and debf=float_of_int deb
		in int_of_float ((xf-.debf)*.rapport)

(* Détermination de l'effectifs des classes *)
in let cree_classes () =
		let result=make_vect (long/tas+1) (-1)
	in for c=0 to (long-1) do
			let indice=calc_classe tab.(c) in
				result.(indice)<-result.(indice)+1
		done;
		for c=1 to (long/tas) do
			result.(c)<-result.(c)+result.(c-1)+1
		done;
		result
in let classes=cree_classes()
in let copie_classes=copy_vect cree_classes

(* Réalisation des cycles *)
in let cycle depart =
		let temp1=ref tab.(depart) and temp2=ref tab.(depart)
		and c=ref depart and d=ref (-1) and a=ref 0
	in while (!d<>depart) do
			a:=calc_classe !temp1; d:=classes.(!a);
			temp2:=tab.(!d); tab.(!d)<- !temp1;
			classes.(!a)<-classes.(!a)-1;
			temp1:= !temp2; c:=!d
		done;
		classes.(!a)<-classes.(!a)+1
	
(* Test si un élément est dans sa classe *)
	and est_ds_classe k = let i=calc_classe tab.(k) in
				if i=0
				then k<=copie_classes.(0)
				else k>copie_classes.(i-1) && k<=copie_classes.(i)

in		for c=0 to (long-1) do
			if not(est_ds_classe c) then cycle c
		done;
		tri_partie tab 0 copie_classes.(0);
		for c=1 to (long/tas) do
			tri_partie tab copie_classes.(c-1) copie_classes.(c)
		done;
		tab
;;

(* Un petit test ... *)
let tab = alea 100000 10000;;
let liste = list_of_vect tab;;
let temp=ref (sys__time());;
sort__sort (prefix <=) liste;;
print_float (sys__time()-. !temp); print_string " s\n"; temp:=sys__time();;
classement tab;;
print_float (sys__time()-. !temp); print_string " s\n"; temp:=sys__time();;