Sorting and Searching
A whole course could be written on sorting and searching alone. Here, for the purpose of illustration, we look at some simple algorithms and their implementation in Pascal.
Sorting - Insertion Sort
An insertion sort is quite an inefficient sort algorithm, but is simple and functional. In an unsorted array of n items, it sorts the items using the following algorithm :
Loop through from array[1] to array[n -1] using counter i
Loop backwards from array[i - 1] to array[0] using counter j
If array[j] < array[j-1] swap array[j] and array[j-1];
It can be seen that to amend the insertion sort to sort in reverse order is trivial. The code for an insertion sort is in the procedure ins_sort in the program below; the main body of the program simply serves to accept the numerical input and present the array of numbers both pre-sort and post-sort.
program insertionsort;
const maxarray = 100;
var num_items, i, n : integer;
var sort_array : array[1..maxarray] of integer;
procedure ins_sort(var num_items : integer);
var i, j, current : integer;
begin
for i := 2 to num_items do
begin
for j := i downto 2 do
begin
if (sort_array[j] < sort_array[j-1]) then begin
current := sort_array[j];
sort_array[j] := sort_array[j-1];
sort_array[j-1] := current;
end;
end;
end;
end;
begin
writeln ('Enter number of items (up to ',maxarray,') to be sorted ');
readln (num_items);
for i := 1 to num_items do begin
write ('Enter list item #',i,' : ');
readln (n);
sort_array[i] := n;
end;
write ('Unsorted array :');
for i := 1 to num_items do write (' ',sort_array[i]);
writeln;
writeln;
ins_sort(num_items);
write ('Sorted array :');
for i := 1 to num_items do write (' ',sort_array[i]);
writeln;
end.
Sorting - Selection Sort
A selection sort starts at the first element of the array to be sorted. It then compares that element with every subsequent element, and, if the lowest value item of the subsequent elements is lower than the first element, switches the lowest value item with the first element. It then proceeds to the second element and so through the array :
Loop through from array[0] to array[n -1] using counter i
Smallest Value = i;
Loop through from array[i + 1] to array[n - 1] using counter j
If array[j] < array[Smallest Value] then Smallest Value = j;
Next j;
Switch Array[i] and Array[Smallest Value]
Next i;
In the code to implement the selection sort that follows, the main procedure is the same as for the insertion sort, except we invoke the sel_sort() procedure rather than the ins_sort() procedure.
program selectionsort;
const maxarray = 100;
var num_items, i, n : integer;
var sort_array : array[1..maxarray] of integer;
procedure sel_sort(var num_items : integer);
var i, j, small, smaller : integer;
begin
for i := 1 to num_items do
begin
smaller := i; { assume this is the smallest until proven otherwise }
for j := i + 1 to num_items do
if (sort_array[j] < sort_array[smaller]) then smaller := j;
if not (smaller = i) then
begin
small := sort_array[i];
sort_array[i] := sort_array[smaller];
sort_array[smaller] := small;
end;
end;
end;
begin
writeln ('Enter number of items (up to ',maxarray,') to be sorted ');
readln (num_items);
for i := 1 to num_items do begin
write ('Enter list item #',i,' : ');
readln (n);
sort_array[i] := n;
end;
write ('Unsorted array :');
for i := 1 to num_items do write (' ',sort_array[i]);
writeln;
writeln;
sel_sort(num_items);
write ('Sorted array :');
for i := 1 to num_items do write (' ',sort_array[i]);
writeln;
end.
Sorting - Bubble Sort
In a bubble sort, the array is traversed a number of times exchanging the values of unordered adjacent cells until the array is in order. Again, this is a relatively inefficient sort, and the array has to be traversed even when completely sorted to confirm that no further exchanges are to take place.
Loop Until (array is traversed without any exchanging of array values)
Loop through from array[0] to array[n - 2] using counter i
If array[i + 1] < array[i], switch array[i+1] and array[i];
Again the code to read in the values is the same as in the previous sort programs, and the implementation of the bubble sort algorithm is in the bub_sort() procedure.
program bubblesort;
const maxarray = 100;
var num_items, i, n : integer;
var sort_array : array[1..maxarray] of integer;
procedure bub_sort(var num_items : integer);
var i, current : integer;
var exchange : boolean;
begin
exchange := true;
while (exchange) do
begin
exchange := false;
for i := 1 to num_items - 1 do
if (sort_array[i + 1] < sort_array[i]) then
begin
exchange := true { an exchange will take place on this traversal }
current := sort_array[i + 1];
sort_array[i + 1] := sort_array[i];
sort_array[i] := current;
end;
end; { end while }
end;
begin
writeln ('Enter number of items (up to ',maxarray,') to be sorted ');
readln (num_items);
for i := 1 to num_items do begin
write ('Enter list item #',i,' : ');
readln (n);
sort_array[i] := n;
end;
write ('Unsorted array :');
for i := 1 to num_items do write (' ',sort_array[i]);
writeln;
writeln;
bub_sort(num_items);
write ('Sorted array :');
for i := 1 to num_items do write (' ',sort_array[i]);
writeln;
end.
Searching
In the findaddr.pas and searchad.pas programs, we performed sequential searchse on the paddress.txt file, reading each record in order and examining the fields to see if the required fields matched the value for which we were searching. This search algorithm was adequate for our purposes, searching a small file, but is very inefficient. Here we will look at some alternative search programs. Most non-sequential searches require the array of items to be searched to be sorted first.
Searching - Binary Search
A binary search requires a sorted array. Initially, start and end values in the array are stored. The value in the middle of these two is then compared with the value being searched for. If the value being searched for is greater than the value in the middle, then the middle value becomes the start value and the binary search starts again. If the value being searched for is less than the value in the middle, then the middle value becomes the end value and the binary search starts again. The algorithm can be written as :
First = First element of array
Last = Last element of array
While (not found)
Middle = (First + Last)/2
Check Middle is an ok array subscript, if not return 0;
If array[Middle] = search_item return Middle
Else if array[Middle] > search_item Last = Middle -1
Else First = Middle + 1
End While
In the code below, we use the bubble sort program to take in the input and sort the array. Then we use the binary search function to search the array for a required value.
program binarysearch;
const maxarray = 100;
var num_items, i, n, found, errmsg : integer;
var sort_array : array[1..maxarray] of integer;
var searchstr : string[10];
procedure bub_sort(var num_items : integer);
var i, current : integer;
var exchange : boolean;
begin
exchange := true;
while (exchange) do
begin
exchange := false;
for i := 1 to num_items - 1 do
if (sort_array[i + 1] < sort_array[i]) then
begin
exchange := true; { an exchange will take place on this traversal }
current := sort_array[i + 1];
sort_array[i + 1] := sort_array[i];
sort_array[i] := current;
end;
end; { end while }
end;
function bin_search (find: integer; num_items : integer): integer;
var first, last, middle : integer;
begin
first := 1;
last := num_items;
middle := 1;
bin_search := 0;
if find = sort_array[first] then bin_search := first
else if find = sort_array[last] then bin_search := last
else
while ((first < last) and (not(sort_array[middle] = find))) do
begin
middle := (first + last) div 2;
if (sort_array[middle] = find) then bin_search := middle
else if (sort_array[middle] < find) then first := middle + 1
else if (sort_array[middle] > find) then last := middle - 1;
end;
end;
begin
writeln ('Enter number of items (up to ',maxarray,') to be sorted ');
readln (num_items);
for i := 1 to num_items do begin
write ('Enter list item #',i,' : ');
readln (n);
sort_array[i] := n;
end;
write ('Unsorted array :');
for i := 1 to num_items do write (' ',sort_array[i]);
writeln;
writeln;
bub_sort(num_items);
write ('Sorted array :');
for i := 1 to num_items do write (' ',sort_array[i]);
writeln;
{ now to search for data }
writeln ('Enter data to search for, carriage return to quit');
readln (searchstr);
while (not(searchstr = '')) do
begin
val (searchstr, i, errmsg);
if (not(errmsg = 0)) then writeln ('Error reading search number')
else begin
found := bin_search (i, num_items);
if (found = 0) then writeln (i,' not found in array')
else writeln (i,' is item number ',found,' in array');
end;
writeln ('Enter data to search for, carriage return to quit');
readln (searchstr);
end;
end.