Paste: Dual Pivot Quicksort array error
Author: | mbishop |
Mode: | modula3 |
Date: | Sat, 12 Sep 2009 05:46:59 |
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));
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;
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.
New Annotation