Paste: Dual Pivot Quicksort Errors

Author:	mbishop
Mode:	modula3
Date:	Sat, 12 Sep 2009 01:05:54

Plain Text |

Delete Paste

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
Mode:	modula3
Date:	Sat, 12 Sep 2009 03:59:59

Plain Text |

Delete Annotation

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

New Annotation

Summary:
Author:
Mode:	textPostgreSQLPowerCenter Parameter Fileactionscriptadaada95ans-forth94antantlrantlr4apacheconfapdlapplescriptaspaspect-jassembly-agcassembly-agsassembly-arm32assembly-m68kassembly-macro32assembly-mcs51assembly-parrotassembly-r2000assembly-x86avroawkbbatchbbjbcelbeanshellbibtexbinsource-agccc#c++cfscriptchillcilclipsclojurecmakecobolcoffeescriptcoldfusioncplex-lpcsscsvcvs-commitddartdjangodockerfiledotdoxygendrawj2ddsssleiffelembperlerlangfactorfhtmlforthfortranfortran90foxprofreemarkergcbasicgettextgherkingnuplotgogradlegroovygsphaskellhaxehexhl7v2hlslhtaccesshtmlhxmli4glicalendariconidlinforminiinno-setupinterlisiojamonjavajava module-infojavaccjavafxjavascriptjcljedit-actionsjflexjhtmljmkjsonjspkotlinlatexlexlilypondlispliterate-haskelllogslogtalklotosluam4macroschedulermailmakefilemaplemarkdownmavenmavscriptmetapostmlmodula3moinmqscmustache-templatemxmlmyghtymysqln3netrexxnqcnsis2objective-cobjectrexxoccamomnimarkopensipsoutlinepascalpatchperlphppikepl-sqlpl-sql9pl1plaintexplantumlpop11postscriptpovraypowerdynamopowershellprogressprologpropertiesprotobufpspptlpurepvwavepyrexpythonqdocrakefilercprdrebolredcoderelax-ng-compactrenderman-ribrestrfcrhtmlroffrpm-specrtfrubyrustrviews#s+sassbtscalaschemesdl/prsgmlshellscriptshtmlsipsippslateslaxsmalltalksmartysmi-mibsparqlsql-loadersqrsquidconfstatasvn-commitswiftswigtcltemplate-toolkittextexinfotldtransact-sqltsptwikityposcripturluscriptvalavbscriptvelocityverilogvhdlvisualbasicvrml2wellknowntextxmlxqxslyabyamlzpt
Body:

Done