[M3devel] Dual Pivot Quicksort problem (FIXED)

[Martin Bishop]

Sorry to keep posting, but I just wanted to say I fixed the problem (it 
isn't even in this code, it was in the insertion sort module.)

Martin Bishop wrote:
> Edited it some more, lots of silly mistakes in that old code.  Now it 
> almost works...it sorts the array sometimes, but other times gives me 
> a bounds error.  Any idea now?
>
> 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.
>
> Martin Bishop wrote:
>> I saw a post on reddit about a Dual Pivot Quicksort, and I translated 
>> the code from Java to Modula-3.  I have it all translated, and it 
>> builds, but I am having boundary issues.  Somewhere on the second 
>> pass, the variable m2 is getting the value -2.  Here's the code:
>>
>> ...
>
>> Right now when I try to run I get:
>>
>> ***
>> *** runtime error:
>> ***    An array subscript was out of range.
>> ***    file "../DualPivot.m3", line 61
>> ***
>>
>> Line 61 is:  IF arr[m1] < arr[m2] THEN
>>
>> Anyone see what is happening? It's probably off by 1 (or more) 
>> errors, but I don't see them.
>>
>>
>
>