Sorting algorithms/Quicksort: Difference between revisions

Content added Content deleted

Inline

Revision as of 23:32, 8 October 2007

In this task, the goal is to sort an array of elements using the 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.

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;

C

void quick(int *left, int *right)
{
  if (right > left) {
    int pivot = left[(right-left)/2];
    int *r = right, *l = left;
    do {
      while (*l < pivot) l++;
      while (*r > pivot) r--;
      if (l <= r) {
        int t = *l;
        *l++ = *r;
        *r-- = t;
      }
    } while (l <= r);
    quick(left, r);
    quick(l, right);
  }
}
void sort(int *array, int length)
{
  quick(array, array+length-1);
}

Forth

defer lessthan ( a@ b@ -- ? )   ' < is lessthan

: mid ( l r -- mid ) over - 2/ -cell and + ;

: exch ( addr1 addr2 -- ) dup @ >r over @ swap ! r> swap ! ;

: partition ( l r -- l r r2 l2 )
  2dup mid @ >r ( r: pivot )
  2dup begin
    swap begin dup @  r@ lessthan while cell+ repeat
    swap begin r@ over @ lessthan while cell- repeat
    2dup <= if 2dup exch >r cell+ r> cell- then
  2dup > until  r> drop ;

: qsort ( l r -- )
  partition  swap rot
  \ 2over 2over - + < if 2swap then
  2dup < if recurse else 2drop then
  2dup < if recurse else 2drop then ;

: sort ( array len -- )
  dup 2 < if 2drop exit then
  1- cells over + qsort ;

IDL

IDL has a powerful optimized sort() built-in. The following is thus merely for demonstration.

function qs, arr
  if (count = n_elements(arr)) lt 2 then return,arr
  pivot = total(arr) / count ; use the average for want of a better choice
  return,[qs(arr[where(arr le pivot)]),qs(arr[where(arr gt pivot)])]
 end

Example:

IDL> print,qs([3,17,-5,12,99])
     -5       3      12      17      99

MAXScript

fn quickSort arr =
(
    less = #()
    pivotList = #()
    more = #()
    if arr.count <= 1 then
    (
        arr
    )
    else
    (
        pivot = arr[arr.count/2]
        for i in arr do
        (
            case of
            (
                (i < pivot):	(append less i)
                (i == pivot):	(append pivotList i)
                (i > pivot):	(append more i)
            )
        )
        less = quickSort less
        more = quickSort more
        less + pivotList + more
    )
)
a = #(4, 89, -3, 42, 5, 0, 2, 889)
a = quickSort a

Python

def quickSort(arr):
    less = []
    pivotList = []
    more = []
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        for i in arr:
            if i < pivot:
                less.append(i)
            elif i > pivot:
                more.append(i)
            else:
                pivotList.append(i)
        less = quickSort(less)
        more = quickSort(more)
        return less + pivotList + more

a = [4, 65, 2, -31, 0, 99, 83, 782, 1]
a = quickSort(a)