From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,5052a1cdc3cdb4ab
X-Google-Attributes: gid103376,public
From: mfb@mbunix.mitre.org (Michael F Brenner)
Subject: Re: Quicksort
Date: 1998/07/31
Message-ID: <6psgfj$e54@top.mitre.org>#1/1
X-Deja-AN: 376671393
References: <01bdbaef$d13c9340$86eba8c2@j.couston>
 <Pine.HPP.3.93.980729151224.6744A-100000@mickey.informatik.uni-stuttgart.de>
Organization: The MITRE Corporation, Bedford Mass.
Newsgroups: comp.lang.ada
Date: 1998-07-31T00:00:00+00:00
List-Id: <comp.lang.ada>

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;