Re: Quicksort

[mfb@mbunix.mitre.org (Michael F Brenner)]

Here is one student's method of programming quicksort downloaded from 
the Net.

  procedure quicksort (start, finish: heap_indices) is

    -- Quicksort the array LIST from left to right.

    highest: constant exacts := exacts (heap_indices'last);
    i:       exacts := exacts (start);
    j:       exacts := exacts (finish);
    left:    exacts := exacts (start);
    right:   exacts := exacts (finish);
    middle:  exacts;

    procedure swap (left, right: exacts) is
      temp: data;
    begin
      copy_datum (source=>get_random (warehouse, heap_indices (left)),
                  target=>temp);
      put_random (warehouse, heap_indices (left),
                  get_random (warehouse, heap_indices (right)));
      put_random (warehouse, heap_indices (right), temp);
    end swap;

  begin
    assert (heap_indices'first = 0);

    if left in 1..right-1 then
      middle := (left+right) / 2;
      assert (middle>0);
      assert (middle<=highest);
      declare
        X: keys;
      begin
        copy_key (get_key (middle), x);
        loop
          loop
            assert (i>0);
            assert (i<=highest);
            exit when get_key (i) >= X;
            i := i+1;
          end loop;
          loop
            -- if j=0 then
            --   os.low_level_display ("start=");
            --   os.low_level_display (heap_indices'image (start));
            --   os.low_level_display (" finish=");
            --   os.low_level_display (heap_indices'image (finish));
            --   os.low_level_display (" i=");
            --   os.low_level_display (exacts'image (i));
            --   os.low_level_display (" j=");
            --   os.low_level_display (exacts'image (j));
            --   os.low_level_display (" left=");
            --   os.low_level_display (exacts'image (left));
            --   os.low_level_display (" right=");
            --   os.low_level_display (exacts'image (right));
            --   os.low_level_display (" middle=");
            --   os.low_level_display (exacts'image (middle));
            -- end if;
            assert (j>0);
            assert (j<=highest);
            exit when X >= get_key (j);
            j := j-1;
          end loop;
          if i<=j then
            swap (i,j);
            i := i+1;
            j := j-1;
          end if;
          exit when i>j; -- Range left..i-1 is < X and j+1..right is > X.
        end loop;
        if left < j     then
          quicksort (start, heap_indices (j));
        end if;
        if i    < right then
          quicksort (heap_indices (i), finish);
        end if;
      end;
    end if;
  end quicksort;