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;