# Paste: Dual Pivot Quicksort Errors

Author: mbishop modula3 Sat, 12 Sep 2009 01:05:54
Plain Text |
```MODULE DualPivot;

IMPORT Insertion, Fmt;

PROCEDURE Sort(VAR arr: ARRAY OF INTEGER) =
BEGIN
SortFromTo(arr, 0, NUMBER(arr));
END Sort;

PROCEDURE SortFromTo(VAR arr: ARRAY OF INTEGER; from, to: INTEGER) =
BEGIN
RangeCheck(NUMBER(arr), from, to);
DualPivotSort(arr, from, to - 1, 3);
END SortFromTo;

PROCEDURE RangeCheck(len, from, to: INTEGER) RAISES {BadArgument, IndexOutOfRange} =
BEGIN
IF from > to THEN
RAISE BadArgument(Fmt.Int(from) & " > " & Fmt.Int(to) & "\n");
END;
IF from < 0 THEN
RAISE IndexOutOfRange("from");
END;
IF to > len THEN
RAISE IndexOutOfRange("to");
END;
END RangeCheck;

PROCEDURE Swap(VAR arr: ARRAY OF INTEGER; i, j: INTEGER) =
VAR temp := arr[i];
BEGIN
arr[i] := arr[j];
arr[j] := temp;
END Swap;

PROCEDURE DualPivotSort(VAR arr: ARRAY OF INTEGER; left, right, div: INTEGER) =
VAR
len := left - right;
third := len DIV div;
m1 := left + third;
m2 := right - third;
piv1: INTEGER;
piv2: INTEGER;
less := left + 1;
great := right - 1;
dist: INTEGER;

BEGIN
IF len < 27 THEN
Insertion.Sort(arr);
END;

IF m1 <= left THEN
m1 := left + 1;
END;

IF m2 >= right THEN
m2 := right - 1;
END;

IF arr[m1] < arr[m2] THEN
Swap(arr, m1, left);
Swap(arr, m2, right);
ELSE
Swap(arr, m1, right);
Swap(arr, m2, left);
END;

piv1 := arr[left];
piv2 := arr[right];

FOR k := less TO great DO
IF arr[k] < piv1 THEN
Swap(arr, k, less + 1);
ELSIF arr[k] > piv2 THEN
WHILE (k < great) AND (arr[great] > piv2) DO
DEC(great);
END;
Swap(arr, k, great - 1);

IF arr[k] < piv1 THEN
Swap(arr, k, less + 1);
END;
END;
END;

dist := great - less;

IF dist < 13 THEN
INC(div);
END;

Swap(arr, less - 1, left);
Swap(arr, great + 1, right);

DualPivotSort(arr, left, less - 2, div);
DualPivotSort(arr, great + 2, right, div);

IF (dist > len - 13) AND (piv1 # piv2) THEN
FOR k := less TO great DO
IF arr[k] = piv1 THEN
Swap(arr, k, less + 1);
ELSIF arr[k] = piv2 THEN
Swap(arr, k, great - 1);

IF arr[k] = piv1 THEN
Swap(arr, k, less + 1);
END;
END;
END;
END;

IF piv1 < piv2 THEN
DualPivotSort(arr, less, great, div);
END;
END DualPivotSort;

BEGIN
END DualPivot.

(*
***
*** runtime error:
***    An array subscript was out of range.
***    file "../DualPivot.m3", line 61
***
*)```

## Annotation: Fixed lots of errors (still broken)

Author: mbishop modula3 Sat, 12 Sep 2009 03:59:59
Plain Text |
```MODULE DualPivot;

IMPORT Insertion, Fmt, IO;

PROCEDURE Sort(VAR arr: ARRAY OF INTEGER) =
BEGIN
SortFromTo(arr, 0, NUMBER(arr));
END Sort;

PROCEDURE SortFromTo(VAR arr: ARRAY OF INTEGER; from, to: INTEGER) =
BEGIN
RangeCheck(NUMBER(arr), from, to);
DualPivotSort(arr, from, to - 1, 3);
END SortFromTo;

PROCEDURE RangeCheck(len, from, to: INTEGER) RAISES {BadArgument, IndexOutOfRange} =
BEGIN
IF from > to THEN
RAISE BadArgument(Fmt.Int(from) & " > " & Fmt.Int(to) & "\n");
END;
IF from < 0 THEN
RAISE IndexOutOfRange("from");
END;
IF to > len THEN
RAISE IndexOutOfRange("to");
END;
END RangeCheck;

PROCEDURE Swap(VAR arr: ARRAY OF INTEGER; i, j: INTEGER) =
VAR temp := arr[i];
BEGIN
arr[i] := arr[j];
arr[j] := temp;
END Swap;

PROCEDURE DualPivotSort(VAR arr: ARRAY OF INTEGER; left, right, div: INTEGER) =
VAR
len := right - left;
third := len DIV div;
m1 := left + third;
m2 := right - third;
piv1: INTEGER;
piv2: INTEGER;
less := left + 1;
great := right - 1;
dist: INTEGER;

BEGIN
IF len < 27 THEN
Insertion.Sort(arr);
RETURN;
END;

IF m1 <= left THEN
m1 := left + 1;
END;

IF m2 >= right THEN
m2 := right - 1;
END;

IO.Put("DEBUG: m1 = " & Fmt.Int(m1) & " m2 = " & Fmt.Int(m2) &
" left = " & Fmt.Int(left) & " right = " & Fmt.Int(right) & "\n");
IO.Put("DEBUG: len = " & Fmt.Int(len) & " third = " & Fmt.Int(third) & "\n");
IO.Put("***\n");

IF arr[m1] < arr[m2] THEN
Swap(arr, m1, left);
Swap(arr, m2, right);
ELSE
Swap(arr, m1, right);
Swap(arr, m2, left);
END;

piv1 := arr[left];
piv2 := arr[right];

FOR k := less TO great DO
IF arr[k] < piv1 THEN
Swap(arr, k, less);
INC(less);
ELSIF arr[k] > piv2 THEN
WHILE (k < great) AND (arr[great] > piv2) DO
DEC(great);
END;
Swap(arr, k, great);
DEC(great);

IF arr[k] < piv1 THEN
Swap(arr, k, less);
INC(less);
END;
END;
END;

dist := great - less;

IF dist < 13 THEN
INC(div);
END;

Swap(arr, less - 1, left);
Swap(arr, great + 1, right);

DualPivotSort(arr, left, less - 2, div);
DualPivotSort(arr, great + 2, right, div);

IF (dist > len - 13) AND (piv1 # piv2) THEN
FOR k := less TO great DO
IF arr[k] = piv1 THEN
Swap(arr, k, less);
INC(less);
ELSIF arr[k] = piv2 THEN
Swap(arr, k, great);
DEC(great);

IF arr[k] = piv1 THEN
Swap(arr, k, less);
INC(less);
END;
END;
END;
END;

IF piv1 < piv2 THEN
DualPivotSort(arr, less, great, div);
END;
END DualPivotSort;

BEGIN
END DualPivot```