Anonymous user
Sorting algorithms/Quicksort: Difference between revisions
no edit summary
No edit summary |
|||
Line 3:
In this task, the goal is to sort an array of elements using the [http://en.wikipedia.org/wiki/Quicksort Quicksort] algorithm. The elements must have a total order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers.
=={{header|Ada}}==
This example is implemented as a generic procedure. The procedure specification is:
-----------------------------------------------------------------------
-- Generic Quicksort procedure
-----------------------------------------------------------------------
generic
type Element_Type is private;
type Index_Type is (<>);
type Element_Array is array(Index_Type range <>) of Element_Type;
with function "<" (Left, Right : Element_Type) return Boolean is <>;
with function ">" (Left, Right : Element_Type) return Boolean is <>;
procedure Sort(Item : in out Element_Array);
The procedure body deals with any discrete index type, either an integer type or an enumerated type.
-----------------------------------------------------------------------
-- Generic Quicksort procedure
-----------------------------------------------------------------------
procedure Sort (Item : in out Element_Array) is
procedure Swap(Left, Right : in out Element_Type) is
Temp : Element_Type := Left;
begin
Left := Right;
Right := Temp;
end Swap;
Pivot_Index : Index_Type;
Pivot_Value : Element_Type;
Right : Index_Type := Item'Last;
Left : Index_Type := Item'First;
begin
if Item'Length > 2 then
Pivot_Index := Index_Type'Val((Index_Type'Pos(Item'Last) + 1 +
Index_Type'Pos(Item'First)) / 2);
Pivot_Value := Item(Pivot_Index);
loop
Left := Item'First;
Right := Item'Last;
while Left < Item'Last and then Item(Left) < Pivot_Value loop
Left := Index_Type'Succ(Left);
end loop;
while Right > Item'First and then Item(Right) > Pivot_Value loop
Right := Index_Type'Pred(Right);
end loop;
exit when Left >= Right;
Swap(Item(Left), Item(Right));
if Left < Item'Last and Right > Item'First then
Left := Index_Type'Succ(Left);
Right := Index_Type'Pred(Right);
end if;
end loop;
if Right > Item'First then
Sort(Item(Item'First..Right));
end if;
if Left < Item'Last then
Sort(Item(Left..Item'Last));
end if;
end if;
end Sort;
An example of how this procedure may be used is:
with Sort;
with Ada.Text_Io;
with Ada.Float_Text_IO; use Ada.Float_Text_IO;
procedure Sort_Test is
type Days is (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
type Sales is array(Days range <>) of Float;
procedure Sort_Days is new Sort(Float, Days, Sales);
procedure Print(Item : Sales) is
begin
for I in Item'range loop
Put(Item => Item(I), Fore => 5, Aft => 2, Exp => 0);
end loop;
end Print;
Weekly_Sales : Sales := (Mon => 300.0,
Tue => 700.0,
Wed => 800.0,
Thu => 500.0,
Fri => 200.0,
Sat => 100.0,
Sun => 900.0);
begin
Print(Weekly_Sales);
Ada.Text_Io.New_Line(2);
Sort_Days(Weekly_Sales);
Print(Weekly_Sales);
end Sort_Test;
=={{header|C}}==
| |||