25f2182ca6
git-svn-id: http://cregut.svn.enseeiht.fr/2020/1sn/pim/projets/GH-05@213640 e13453a9-b01f-0410-a051-f404c4f0c485
95 lines
2.7 KiB
Ada
95 lines
2.7 KiB
Ada
package body Quicksort is
|
|
|
|
procedure sort(vec: in out Vector_Element.T_Vecteur; low: Natural := 0; high: Natural := Vector_Element.Capacite-1) is
|
|
|
|
procedure swap(left, right: Natural) is
|
|
tmp : constant T_Reel := vec(left);
|
|
begin
|
|
vec(left) := vec(right);
|
|
vec(right) := tmp;
|
|
end swap;
|
|
|
|
pivot : constant T_Reel := vec(low);
|
|
right : Natural := high;
|
|
left : Natural := low;
|
|
|
|
begin
|
|
if high - low > 0 then
|
|
loop
|
|
while left < right and pivot >= vec(left) loop
|
|
left := left + 1;
|
|
end loop;
|
|
while pivot < vec(right) loop
|
|
right := right - 1;
|
|
end loop;
|
|
|
|
exit when right <= left;
|
|
|
|
swap(left, right);
|
|
left := left + 1;
|
|
right := right - 1;
|
|
end loop;
|
|
|
|
if right = high then
|
|
right := right - 1;
|
|
swap(low, high);
|
|
end if;
|
|
|
|
if left = low then
|
|
left := left - 1;
|
|
end if;
|
|
|
|
sort(vec, low, right);
|
|
sort(vec, left, high);
|
|
end if;
|
|
end sort;
|
|
|
|
procedure sort(vec: in out Vector_Element.T_Vecteur; vec_index: in out Vector_Index.T_Vecteur;
|
|
low: Natural := 0; high: Natural := Vector_Element.Capacite-1) is
|
|
|
|
procedure swap(left, right: Natural) is
|
|
tmp : constant T_Reel := vec(left);
|
|
tmp_index : constant T_Entier := vec_index(left);
|
|
begin
|
|
vec(left) := vec(right);
|
|
vec(right) := tmp;
|
|
vec_index(left) := vec_index(right);
|
|
vec_index(right) := tmp_index;
|
|
end swap;
|
|
|
|
pivot : constant T_Reel := vec(low);
|
|
right : Natural := high;
|
|
left : Natural := low;
|
|
|
|
begin
|
|
if high - low > 0 then
|
|
loop
|
|
while left < right and pivot >= vec(left) loop
|
|
left := left + 1;
|
|
end loop;
|
|
while pivot < vec(right) loop
|
|
right := right - 1;
|
|
end loop;
|
|
|
|
exit when right <= left;
|
|
|
|
swap(left, right);
|
|
left := left + 1;
|
|
right := right - 1;
|
|
end loop;
|
|
|
|
if right = high then
|
|
right := right - 1;
|
|
swap(low, high);
|
|
end if;
|
|
|
|
if left = low then
|
|
left := left - 1;
|
|
end if;
|
|
|
|
sort(vec, vec_index, low, right);
|
|
sort(vec, vec_index, left, high);
|
|
end if;
|
|
end sort;
|
|
|
|
end Quicksort; |