Contents :

  Search & Sort.

Exercises :

• (D1) Array Sorting
• (S1)
• (S2)
• (S3)
• (X1)
• (H1)
• (H2)
• (T1)

D1: Array Sorting.

MODULE D1;
  FROM IO IMPORT WrInt, WrLn, WrStr;

  (* SORTING ALGORITHM *)
  (* ================= *)
  PROCEDURE QuickSortIntArray(VAR a: ARRAY OF INTEGER);
    (* this code is copied from Tiberghiens course *)

    PROCEDURE Swap(i, j:CARDINAL);
      VAR t: INTEGER;
    BEGIN
       t := a[i]; a[i] := a[j]; a[j] := t;
    END Swap;

    PROCEDURE QuickSort(L, H:CARDINAL);
      VAR i, j:CARDINAL;
        pivot: INTEGER;
    BEGIN
      i := L;
      j := H;
      pivot := a[(L+H) DIV 2];
      REPEAT
        WHILE a[i] < pivot DO
          INC(i);
        END;
        WHILE a[j] > pivot DO
          DEC(j);
        END;
        IF i <= j THEN
          Swap(i, j);
          INC(i);
          DEC(j);
        END;
      UNTIL i > j;
      IF L < j THEN
        QuickSort(L, j);
      END;
      IF H > i THEN
        QuickSort(i, H);
      END;
    END QuickSort;

  BEGIN
    QuickSort (0, HIGH(a));
  END QuickSortIntArray;

  (* THE ARRAY TO BE SORTED *)
  (* =======================*)
  PROCEDURE WrIntArray(arr: ARRAY OF INTEGER);
    VAR i: CARDINAL;
  BEGIN
    FOR i := 0 TO HIGH(arr) DO
      WrInt(arr[i], 5);
    END;
    WrLn;
  END WrIntArray;

  CONST ARRAY_SIZE = 20;
  VAR
    arr: ARRAY[1..ARRAY_SIZE] OF INTEGER;
    i: CARDINAL;
BEGIN
  arr[1] := 89; arr[2] := -100; arr[3] := 0; arr[4] := 65; arr[5] := 78;
  arr[6] := 2; arr[7] := 3; arr[8] := -8; arr[9] := 65; arr[10] := -45;
  arr[11] := -14; arr[12] := -56; arr[13] := -36; arr[14] := -1; arr[15] := 5;
  arr[16] := -97; arr[17] := 56; arr[18] := 4; arr[19] := 2; arr[20] := 32;

  WrStr("Array before sorting: ");
  WrIntArray(arr);

  QuickSortIntArray(arr);

  WrStr("Array after sorting: ");
  WrIntArray(arr);

END D1.

Parts of the sort algorithm that you should adapt to sort a different datastructure:

1. Swap procedure
2. pivot type
3. the 2 compares

S1

S2

S3

X1

H1

H2

T1