CS 131 LECTURE 13 - INTERNAL SORTING ALGORITHMS

Sorting Package Specification

GENERIC
  TYPE Elements IS PRIVATE;
  TYPE Keys IS PRIVATE;
  TYPE Tables IS ARRAY(Integer RANGE <>) OF
    Elements;
  WITH FUNCTION Get_Key(Element: Elements)
    RETURN Keys;
  WITH FUNCTION "<"(Left,Right: Keys)
    RETURN Boolean IS <>;
PACKAGE Sorting_Package IS
  PROCEDURE Insertion_Sort(Table: IN OUT
    Tables);
  PROCEDURE Selection_Sort(Table: IN OUT
    Tables);
  PROCEDURE Bubble_Sort(Table: IN OUT
    Tables);
  PROCEDURE Merge_Sort(Table: IN OUT
    Tables);
  PROCEDURE Quick_Sort(Table: IN OUT
    Tables);
  PROCEDURE Heap_Sort(Table: IN OUT Tables);
END Sorting_Package;

Sorting Package Body

PACKAGE BODY Sorting_Package IS
  PROCEDURE Swap(Left,Right: IN OUT
    Elements) IS
    Temp: Elements := Left;
  BEGIN
    Left := Right;
    Right := Temp;
  END Swap;
  PROCEDURE Rotate(Table: IN OUT Tables) IS
    Temp: Elements := Table(Table'Last);
  BEGIN
    Table(Table'First+1..Table'Last) :=
      Table(Table'First..Table'Last-1);
    Table(Table'First) := Temp;
  END Rotate;
 
  -- Separate Declarations
  -- For All The Sorts
 
END Sorting_Package;

Important Points:

1. The Swap Procedure Is Used By Many Of The Sort Routines

2. The Rotate Procedure Is Used By The Insertion Sort

Insertion Sort Procedure

SEPARATE (Sorting_Package)
PROCEDURE Insertion_Sort(Table: IN OUT
   Tables) IS
  J: Integer;
BEGIN
  FOR I IN Table'First+1..Table'Last LOOP
    J := I - 1;
    WHILE Get_Key(Table(I)) <
      Get_Key(Table(J)) LOOP
      J := J -1;
      EXIT WHEN J < Table'First;
    END LOOP;
    IF I > J + 1 THEN
        Rotate(Table(J+1..I));
    END IF;
  END LOOP;
END Insertion_Sort;

Selection Sort Procedure

SEPARATE (Sorting_Package)
PROCEDURE Selection_Sort(Table: IN OUT
    Tables) IS
  Minimum : Integer;
BEGIN
  FOR I IN Table'First..Table'Last-1 LOOP
    Minimum := I;
    FOR J IN I+1..Table'Last LOOP
      IF Get_Key(Table(J)) <
        Get_Key(Table(Minimum)) THEN
        Minimum := J;
      END IF;
    END LOOP;
    Swap(Table(I),Table(Minimum));
  END LOOP;
END Selection_Sort;

Bubble Sort Procedure

SEPARATE (Sorting_Package)
PROCEDURE Bubble_Sort(Table: IN OUT Tables)
IS
BEGIN
  FOR I IN Table'First..Table'Last-1 LOOP
    FOR J IN REVERSE I+1..Table'Last LOOP
      IF Get_Key(Table(J)) <
        Get_Key(Table(J-1)) THEN
        Swap(Table(J),Table(J-1));
      END IF;
    END LOOP;
  END LOOP;
END Bubble_Sort;
 

Important Points:

1. The Best Case Is When The Data Is Already Sorted, The Worst Case Is Inversely Sorted

2. Although The Big-O For All Algorithms Is The Same In The Average Case, In Practice The Insertion Sort Is Best And The Selection Sort Is Second Best

All Algorithms

Overall Performance: O(1)

Important Point:

1. The Big-O Will Be O(1) Unless There Is Either Recursion Or Explicit Dynamic Memory Allocation

Merge Sort Procedure

SEPARATE (Sorting_Package)
PROCEDURE Merge_Sort(Table: IN OUT Tables)
IS
  Middle: Integer;
  Temp: Tables(Table'Range);
  PROCEDURE Merge(Get,Put: IN OUT Tables;
    Mid: IN Integer) IS SEPARATE;
BEGIN
  IF Table'First < Table'Last THEN
    Middle := (Table'First + Table'Last)/2;
    Merge_Sort(Table(Table'First..Middle));
    Merge_Sort(Table(Middle+1..Table'Last));
    Merge(Table,Temp,Middle);
    Table := Temp;
  END IF;
END Merge_Sort;

Merge Procedure

SEPARATE (Sorting_Package.Merge_Sort)
PROCEDURE Merge(Get,Put: IN OUT Tables;
  Mid: IN Integer) IS
  Left,Index: Integer := Get'First;
  Right: Integer := Mid + 1;
BEGIN
  WHILE Left <= Mid AND Right <= Get'Last
  LOOP
    IF Get_Key(Get(Left)) <
      Get_Key(Get(Right)) THEN
      Put(Index) := Get(Left);
      Left := Left + 1;
    ELSE
      Put(Index) := Get(Right);
      Right := Right + 1;
    END IF;
    Index := Index + 1;
  END LOOP;
  FOR Left_Index IN Left..Mid LOOP
    Put(Index) := Get(Left_Index);
    Index := Index + 1;
  END LOOP;
  FOR Right_Index IN Right..Get'Last LOOP
    Put(Index) := Get(Right_Index);
    Index := Index + 1;
  END LOOP;
END Merge;

Quick Sort Procedure

SEPARATE (Sorting_Package)
PROCEDURE Quick_Sort(Table:IN OUT Tables) IS
  Pivot: Integer;
  PROCEDURE Split(Table: IN OUT Tables;
    Pivot: OUT Integer) IS SEPARATE;
BEGIN
  IF Table'First < Table'Last THEN
    Split(Table,Pivot);
    Quick_Sort(Table(Table'First..Pivot-1));
    Quick_Sort(Table(Pivot+1..Table'Last));
  END IF;
END Quick_Sort;

Important Point:

1. The Split Procedure Does Not Necessary Split The File In The Middle

Split Procedure

SEPARATE (Sorting_Package.Quick_Sort)
PROCEDURE Split(Table: IN OUT Tables;
  Pivot: OUT Integer) IS
  Key: Keys:= Get_Key(Table(Table'First));
  Left: Integer := Table'First + 1;
  Right: Integer := Table'Last;
BEGIN
  LOOP
    WHILE Left <= Right AND THEN NOT
      (Key < Get_Key(Table(Left))) LOOP
      Left := Left + 1;
    END LOOP;
    WHILE Left <= Right AND THEN
      Key < Get_Key(Table(Right)) LOOP
      Right := Right - 1;
    END LOOP;
    IF Left < Right THEN
      Swap(Table(Left),Table(Right));
      Left := Left + 1;
      Right := Right - 1;
    END IF;
    EXIT WHEN Left > Right;
  END LOOP;
  Swap(Table(Table'First),Table(Right));
  Pivot := Right;
END Split;

Heap Sort Procedure

WITH Sift;
SEPARATE (Sorting_Package)
PROCEDURE Heap_Sort(Table: IN OUT Tables) IS
  PROCEDURE Re_Heap IS NEW Sift(Elements,
    Keys,Tables,Get_Key);
BEGIN
  FOR I IN REVERSE Table'First..Table'Last/2
  LOOP
    Re_Heap(Table(I..Table'Last));
  END LOOP;
  FOR I IN REVERSE Table'First..Table'Last-1
  LOOP
    Swap(Table(I + 1),Table(Table'First));
    Re_Heap(Table(Table'First..I));
  END LOOP;
END Heap_Sort;
 

Important Points:

1. The Worst Case For Quick Sort Is When The Splits Always Occur At The Ends

2. Although The Big-O For All Algorithms Is The Same In The Average Case, In Practice The Quick Sort Is Best And The Heap Sort Is Second Best