Sorts

Bubble Sort:

procedure sort ( var v: ArrayToStart; lo, up : int)

var i,j : int;
tempr : ArrayEntry;

begin
while up > lo do begin
          j = lo;

for i = lo to up - 1 do
   if r[i].k > r[i+1].k then begin
             tempr = r[i];
             r[i] = r[i+1];
             r[i+1] = tempr;
             j = i;
             end;
     up = j;
    end;
end;


2-way Bubble Sort:

sort ( r , lo , up )
ArrayToStart r;
int lo, up;

{ int i,j;
  while ( up > lo )  {
         j = lo;
         for ( i = lo; i < up; i++ ) {
               if ( r[i].k > r[i+1].k)
                       exchange ( r , i, i+1);
                      j = i; }
         up = j;
         for ( i = up; i > lo; i-- ) {
               if ( r[i].k < r[i-1].k)
                        exchange (r, i, i-1);
                        j = i; }
         lo = j;
       }
}

Linear Insertion Sort:

sort ( r , lo , up );
ArrayToSort r;
int lo, up;

{ int i,j;
   ArrayEntry tempr;
   for ( i = up - 1; i >= lo; i --) {
    tempr = r[i];
    for (j = i+1; j <= up && (tempr.k > r[j].k ; j ++)
                 r [j-1] = r [j];
    r[j-1]=tempr;
 }
};

Linear Insertion Sort with Sentinel :

sort ( r , lo , up )
ArrayToStart r;
int lo, up;
{int i,j;
ArrayEntry tempr;
 r[up+1].k = MaximumKey;
for ( i = up - 1; i >= lo; i --) {
    tempr = r[i];
    for (j = i+1;  tempr.k > r[j].k ; j ++)
                 r [j-1] = r [j];
    r[j-1]=tempr;
 }
}

Quicksort:

procedure sort ( var r: ArrayToSort; lo, up: int );

var i,j: int;
tempr: ArrayEntry;

begin
while up> lo do begin
   i = lo;
   j = up;

  tempr = r[lo];
  while i < j do begin
    while r[j].k > tempr.k do
           j = j - 1;
     r[i] = r[j];
     while (i < j) && (r[i].k <= tempr.k) do
                i += 1;
      r[j] = r[i];
     end;
 r[i] = tempr;
 sort ( r, lo, i-1);
 lo = i + 1;
 end;
end;

Shellsort:

sort ( r, lo, up )
ArrayToStart r;
int lo, up;

{ int d,i,j;
  ArrayEntry tempr;
  for ( d = up - lo + 1; d>1;) {
              if (d<5)   d = 1;
                  else d = (5*d - 1)/11;
              for(i=up-d; i>=lo;i--) {
                  tempr = r[i];
                  for ( j=i+d;j<=up && (tempr.k>r[j].k);j+=d )
                              r[j-d] = r[j];
                 r[j-d]=tempr;
                }
        }
}

Heapsort:

procedure sort(var r: ArrayToSort ; lo, up : int)

var i : int;
      tempr : ArrayEntry;

begin
  for i = (up / 2 ) downto 2  do siftup ( r, i, up);
  for i = up downto 2 do begin
            siftup ( r, 1, i);
            tempr = r[1];
            r[1] = r[i];
           r[i] = tempr;
         end;

procedure siftup ( var r : RecordArray; i,n: int)
var j:int;
     tempr: ArrayEntry;
begin
     while 2*i<=n do begin
              j = 2*i;
              if j < n then
                     if r[j].k < r[j+1].k then j+=1;
              if r[i].k < r[j].k then begin
                     tempr = r [j];
                    r[j] = r[i];
                     r[i] = tempr;
                    i = j;
                   end;
                else i = n + 1;
               end;
   end;


Linear Probing Sort:

Global variables:

UppBoundr: int
Assert(m+w <= UppBoundr)
m: int
m = Size of interpolation area.
w = desired overflow area.

procedure sort ( var r : ArrayToSort; lo, up : int )

var i,j,uppr : int;
     r1: ArrayToSort;

begin
 uppr = up + ( UppBoundr - up ) * 3 div 4;
 r1 = r;

for j = lo to UppBoundr do r[j].k = NoKey;
for j = lo to up do begin
        i = phi ( r1[j].k, lo, uppr);
       while r[i].k != NoKey do begin
            if r1[j].k < r[i].k then begin
                    r1[j-1] = r[i];
                    r[i] = r1[j];
                    r1[j] = r1[j-1];
                  end;
             i+=1;
        if i > UppBoundr then Error
                end;
    r[i] = r1[j];
   end;
i = 0;
for j = lo to UppBoundr do
 if r[j].k != NoKey then begin
           i += 1;
           r[i] = r[j];
          end;
for j=i+1 to UppBoundr do r[j].k = NoKey
 end;

phi ( key, lo, up )
typekey key;
int lo, up;
{int i;
  i = ( key - MinKey ) * ( up - lo + 1 ) / ( MaxKey - MinKey ) + lo;
  return ( i > up ? up : i < lo ? lo : i );
};


Merge Sort:
Quick Sort:

  
COMING SOON