[M3devel] Dual Pivot Quicksort problem

[Martin Bishop]

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.
>
>