Work made for Algorithms and Data Structures, INPE, Brazil, 2000 by Dmitry V. Fedorov.

Sorting Algorithms

Bubble Sort

This is one of the simplest sorting algorithms and also the slowest one.

Definition:
Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done.

Algorithm:

procedure BubbleSort(var A: array of Integer);
var
  I, J, T: Integer;
begin
  for I := High(A) downto Low(A) do
    for J := Low(A) to High(A) - 1 do
      if A[J] > A[J + 1] then
      begin
        T := A[J];
        A[J] := A[J + 1];
        A[J + 1] := T;
      end;
end;

The algorithm consists of two nested loops. The index J in the inner loop travels up the array, comparing adjacent entries in the array (at J and J+1), while the outer loop causes the inner loop to make repeated passes through the array. In this case after the first pass, the largest element is guaranteed to be at the end of the array, after the second pass, the second largest element is in position, and so on.

Example:
7 4 1 9 2
4 1 7 2 9
1 4 2 7 9
1 2 4 7 9

Time Complexity:
Complexity is O(n**2) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning.

Selection Sort

Definition:
This algorithm orders items by repeatedly looking through remaining items to find the least one and moving it to a final location.

Algorithm:

procedure SelectionSort(var A: array of Integer);
var
  I, J, T: Integer;
begin
  for I := Low(A) to High(A) - 1 do
    for J := High(A) downto I + 1 do
      if A[I] > A[J] then
      begin
        T := A[I];
        A[I] := A[J];
        A[J] := T;
      end;
end;

Rather than swapping neighbors continuously like the Bubble Sort, this algorithm finds the smallest element of the array and interchanges it with the element in the first position of the array. After that it reexamines the remaining elements in the array to find the second smallest element. The element which is found is interchanged with the element in the second position of the array. This process continues until all elements are placed in their proper order.

Example:
7 4 1 9 2
1 4 7 9 2
1 2 7 9 4
1 2 4 9 7
1 2 4 7 9

Time Complexity:
The number of element interchanges depends on how unsorted the array is. During each pass no more that one interchange is essential thus the maximum number of interchanges for this sort is n -1.
Thus, the total number of comparisons is proportional to O(n2).
Worst Case : n2/4.
Average Case : n2/4

Quick Sort

This is probably the quickest and mostly used way to sort an array of objects.

Definition:
An in-place sort algorithm that uses the divide and conquer paradigm. It picks an element from the array (the pivot), partitions the remaining elements into those greater than and less than this pivot, and recursively sorts the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.

Algorithm:

procedure QuickSort(var A: array of Integer);

  procedure DoQuickSort(var A: array of Integer; iLo, iHi: Integer);
  var
    Lo, Hi, Mid, T: Integer;
  begin
    Lo := iLo;
    Hi := iHi;
    Mid := A[(Lo + Hi) div 2];
    repeat
      while A[Lo] < Mid do Inc(Lo);
      while A[Hi] > Mid do Dec(Hi);
      if Lo <= Hi then
      begin
        T := A[Lo];
        A[Lo] := A[Hi];
        A[Hi] := T;
        Inc(Lo);
        Dec(Hi);
      end;
    until Lo > Hi;
    if Hi > iLo then DoQuickSort(A, iLo, Hi);
    if Lo < iHi then DoQuickSort(A, Lo, iHi);
  end;

begin
  DoQuickSort(A, Low(A), High(A));
end;

The Quick Sort algorithm works by recursively partitioning a list into smaller and smaller sublists until each sublist contains only one member. During each recursion, the two sublists contain those elements of the original list which are: (1) smaller than, and (2) larger that a test element (pivot). The test (pivot) element can be any of the included elements -- usually an element from the middle of the list.

Presented algorithm takes the first test element (pivot = Mid) dividing array length by 2 also as all other partitions. It uses to pointers Lo and Hi. In the beginning Lo starts in the first position and Hi in the last one. Then they will approximate to each other and to Mid swapping elements to right order until Lo is bigger then Hi. Then the recursive calls are made with a new Low and High positions.

Time Complexity:
Worst Case running time O(n2).
Average Case : O(n log n).

Note:
In practical situations, a finely tuned implementation of quicksort beats most sort algorithms, including sort algorithms whose theoretical complexity is O(n log n) in the worst case.

Radix sort

This is the algorithm used by letter-sorting machines in the post office. It is efficient in string data sorting.

Definition:
This algorithm sorts the elements by its digits. Suppose an element of n digits (ex: Post Index), it will appear like : Dn, Dn-1, … , D2, D1. In the first interaction Radix will sort elements by less significant digit (D1) then by more significant D2 until most significant Dn. For sort digits any algorithm may be used (ex: BubbleSort, CountingSort, etc.). In our case is used a variant of Bubble Sort already presented.

Algorithm:

// simulation for Integer array sorting
procedure RadixSort(var A: array of Integer);

  // Create 8 digit Array from Integer Array
  procedure I2SArrayCreate(A: array of Integer; var B : TStringArray);
  var
    i : Integer;
  begin
    SetLength(B, Length(A));
    for i := 0 to Length(A) - 1 do B[i] := Format('%8.8d', [A[i]]);
  end;

  // Create Integer Array from 8 digit Array
  procedure S2IArrayCreate(B : TStringArray; var A: array of Integer);
  var
    i : Integer;
  begin
    for i := 0 to Length(B) - 1 do A[i] := StrToInt(B[i]);
  end;

  procedure BubbleSortColumn(var A: TStringArray; Digit : Integer);
  var
    I, J: Integer;
    TempStr : String;
  begin
    for I := High(A) downto Low(A) do
      for J := Low(A) to High(A) - 1 do
        if A[J][Digit] > A[J + 1][Digit] then
        begin
          TempStr := A[J];
          A[J] := A[J+1];
          A[J+1] := TempStr;
        end;
  end;

var
  DigitsArray : TStringArray;
  i : Integer;
begin
  I2SArrayCreate(A, DigitsArray);
  for i := Digits-1 downto 0 do
    BubbleSortColumn(DigitsArray, i);
  S2IArrayCreate(DigitsArray, A);
end;

In this case integer array is converted into string array and back by I2SarrayCreate and S2IArrayCreate. Then it starts sorting less significant digit then more significant till most significant digit.

Time Complexity:

Since keys are not compared against each other, sorting time is O(cn), where c depends on the size of the key.

Example:
329, 457, 657, 839, 436
436, 457, 657, 329, 839
329, 436, 839, 457, 657
329, 436, 457, 657, 839

 

Searching Algorithms


Sequential Search

This is a simplest and slowest way of finding any value in a list.

Definition:
It simply goes through a list and check if the value is found. It may be used in any kind of arrays, sorted or not.

Algorithm:

function SeqSearch( key : typekey; var r : dataarray ) : integer;
var 
  i : integer;
begin
  i := 1;
  while (key <> r[i].k) and (i < n) do i := i + 1;
  if (r[i].k = key) then search := i  // key found
  else search := -1;
end;

In this case n is an Array size.

Time Complexity:
Run time is O(n).


Binary search

Definition:
It begins with an interval covering the whole array. If the search value is less than the item in the middle of the interval, break the interval to the lower half. Otherwise break it to the upper half. Repeatedly check until the value is found or the interval is empty. This also may be solved using recursive algorithm.

Algorithm:

function BinarySearch( key : typekey; var r : dataarray ) : integer;
var 
  high, j, low : integer;
begin
  low := 0;
  high := n;
  while (high-low > 1) do 
  begin
    j := (high + low) div 2;
    if key <= r[j].k then high := j
    else low  := j
  end;
  if r[high].k = key then search := high  // key found
  else search := -1;                      // key not found
end;

In this case n is an Array size.

Time Complexity:
Run time is O(ln n).

 

Bibliography

1) The Internet

2) Borland Delphi Demo Programs. http://www.borland.com/delphi/

3) Notas de Aula de Complexidade de Algoritmos, Flavio Keidi Miyazawa, Instituto de Computação, Universidade Estadual de Campinas

4) Introduction to Algorithms, Cormen, Leiserson, Rivest.

5) Dictionary of Algorithms, Data Structures, and Problems. http://hissa.nist.gov/dads/