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/