-------------------------------------------------------------------------------
--                                                                           --
--  Ada Interface to the X Window System and Motif(tm)/Lesstif               --
--  Copyright (c) 1996-2000 Hans-Frieder Vogt                                --
--                                                                           --
--  This program is free software; you can redistribute it and/or modify     --
--  it under the terms of the GNU General Public License as published by     --
--  the Free Software Foundation; either version 2 of the License, or        --
--  (at your option) any later version.                                      --
--                                                                           --
--  This program is distributed in the hope that it will be useful,          --
--  but WITHOUT ANY WARRANTY; without even the implied warranty of           --
--  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                     --
--  See the GNU General Public License for more details.                     --
--                                                                           --
--  You should have received a copy of the GNU General Public License        --
--  along with this program; if not, write to the                            --
--  Free Software Foundation, Inc.,                                          --
--  59 Temple Place - Suite 330,                                             --
--  Boston, MA 02111-1307, USA.                                              --
--                                                                           --
--                                                                           --
--  X Window System is copyrighted by the X Consortium                       --
--  Motif(tm)       is copyrighted by the Open Software Foundation, Inc.     --
--                                                                           --
--                                                                           --
-------------------------------------------------------------------------------

-------------------------------------------------------------------------------
--
-- HISTORY:
--          June 20, 1998 begin of history
--
-------------------------------------------------------------------------------

procedure Quick_Sort (C : in out Collection) is

   procedure Sort (Left, Right : in Index);

   procedure Sort (Left, Right : in Index) is
      I, J    : Index;
      Temp, X : Item;
   begin
      I := Left;
      J := Right;
      X := C(Index'Val ((Index'Pos (Left) + Index'Pos (Right)) / 2));
      loop
         while C (I) < X loop
            I := Index'Succ (I);
         end loop;
         while X < C (J) loop
            J := Index'Pred (J);
         end loop;
         if I < J then
            Temp  := C (I);
            C (I) := C (J);
            C (J) := Temp;
            I := Index'Succ (I);
            J := Index'Pred (J);
         elsif I = J then
            if I < Right then
               I := Index'Succ (I);
            end if;
            if J > Left then
               J := Index'Pred (J);
            end if;
            exit;
         else
            exit;
         end if;
      end loop;
      if Left < J then
         Sort (Left, J);
      end if;
      if I < Right then
         Sort (I, Right);
      end if;
   end Sort;

begin
   Sort (C'First, C'Last);
end Quick_Sort;