What's so good?

Fewer Lines of Code (5x typical; 7.5x here)

Quicksort in Prolog:

(from Clocksin & Mellish "Programming in Prolog)
  quisort([ ],X,X).
  quisort([Head|Tail],S,X) :-
      split( Head,Tail,A,B),
      quisort( A,S,[Head|Y] ),
      quisort( B,Y,X ).

  split(H,[A|X],[A|Y],Z) :-
      order(A,H),
      split(H,X,Y,Z).
  split(H,[A|X],Y,[A|Z]) :-
      not( order(A,H) ),
      split( H,X,Y,Z ).
  split(_,[ ],[ ],[ ]).


Quicksort in Pascal

(from Tenenbaum & Augenstein "Data Structures Using Pascal")
  procedure quick2( var x: arraytype; n: aptr);
    type stackitem = record
           lb: aptr2;
           ub: aptr2
         end;
         stack = record
           top: 0..numelts;
           item: array[1..numelts] of stackitem
         end;
    var s: stack;
        newbnds: stackitem;
        i,j: aptr;

    procedure rearrange( lb,ub: aptr2: var j: aptr);
      var up,down: aptr;
          a: integer;
      begin {procedure rearrange}
        a:=x[lb];
        j:=lb;
        up:=ub;
        down:=lb;
        repeat
          while( up > down ) and (x[up] >= a)
            do up:=up-1;
          j:=up;
          if up <> down;
            then begin
                   x[down]:=x[up];
                   while( down < up ) and (x[down] <= a)
                     do down:=down+1;
                   if down <> up
                     then x[up]:=x[down]
                 end {then begin}
        until down=up;
        x[j]:=a
      end; {procedure rearrange}

  function empty (s: stack): boolean;
  begin
    if s.top = 0;
      then empty := true;
      else empty := false
  end {function empty};

  procedure push( var s: stack; x: integer);
  begin
    if s.top = maxstack
      then error('stack overflow')
      else begin
             s.top := s.top + 1;
             s.item[s.top]:=x
           end {else begin}
  end {procedure push}

  function pop( var s: stack): integer;
  begin
    if empty(s)
      then error('stack underflow')
      else begin
             pop:=s.item[s.top];
             s.top:=s.top - 1
           end {else begin}
  end {function pop}; 


  begin {procedure quicksort}
    s.top:=0;
    with newgnds
      do begin
        lb:=1;
        ub:=n;
        push(s,newbnds);
        while not empty(s)
          do begin
            popsub(s,newbnds);
            while ub > lb
              do begin
                rearrange(lb,ub,j);
                if j - lb > ub -j
                  then begin
                    i:=ub;
                    ub:=j-1;
                    push(s,newbnds);
                    lb:=j+1;
                    ub:=i
                  end {then begin}
                    i:=lb;
                    lb:=j+1;
                    push(s,newbnds);
                    lb:=i;
                    ub:=j-1
                  else begin
                  end {else begin}
              end; { while ub > lb }
          end; { while not empty }
      end; { with do begin }

  end {procedure quicksort}

Previous Next