The Algorithms Page




Here is where you will find a wealth of algorithms that can be applied to many different problems. The main types of algorithms that you will find here will be basic algorithms for searching, sorting, graph theory, and some graphics algorithms. Well, lets get to some algorithms!




Sorting

Quicksort
Worst case:O(n2)
Average:O(n*log n)
Description: The basic theory behind the Quicksort algorithm is that the list of items is split and then each list is then quicksorted which causes each sublist to be split and quicksorted, etc. Naturally this is a recursive algorithm and requires 2 procedures to execute, one for the Quicksort algorithm and one to split the list. Now, the list must be split in such a way that all items to the left the split point are smaller than the value at the split point and all items to the right of the split point are greater than the value of the split point
Algorithm: 
(* Splits 'a' into two parts and returns the split point *)
function Split (var a: array of integer; lo, hi: integer):integer;
var
  value, temp: integer;
  up, down: integer;
begin
  up := lo;
  down := hi;
  value := a[lo];

  repeat
    while (a[up] <= value) do
      up := up + 1;
    while (a[down] > value) do
      down := down + 1;

    if (up < down) then
    begin
      temp := a[up];
      a[up] := a[down];
      a[down] := temp;
    end;
  until (up >= down);

  temp := a[lo];
  a[lo] := a[down];
  a[down] := temp;

  Split := down;
end;

procedure QuickSort (var a: array of integer; lo, hi: integer);
var
  splitpoint: integer;
begin
  if (lo < hi) then
  begin
    splitpoint := Split (a, lo, hi);
    QuickSort (a, lo, splitpoint-1);
    QuickSort (a, splitpoint+1, hi);
  end;
end;

JeffSort
Worst case:O(1)
Average case:O(1)
Description: Yes, that's right an order of one sorting algorithm. So what's the catch? Well, it only works on integers in a fixed range, but that's okay since in computer science we usually only deal with numbers in a fixed range anyways (0..255, or 0..32767, etc). As you will see, this is a slight modification of a shell sort algorithm. The basic theory is that it keeps track of the number of occurances of each number and then goes through and writes each number whatever number of occurances that were in the array. You may be asking yourself why it's order of one, and the answer is simple. First we usually assume that the range of numbers is much bigger than the size of the sample and the range is constant. This fact that the range is constant is what makes this a constant time sorting algorithm. The 'true' order is O(Range+N), but since Range is much bigger than N, it's O(Range), and since the Range is constant it's O(1).
Algorithm: 
procedure JeffSort (var a: array of integer; lo, hi, 
                    rangelo, rangehi: integer);
var
  JeffCount: array [rangelo..rangehi] of integer;
  i, j: integer;
begin
  for i:=rangelo to rangehi do
    JeffCount[i] := 0;

  for i:=lo to hi do
    inc (JeffCount[a[i]]);

  for i:=rangelo to rangehi do
    if (JeffCount[i] > 0) then
      for j := 1 to JeffCount[i] do
      begin
        a[lo] := i;
        inc (lo);
      end;
end;
1