The ability to swap the values of two variables is central to most
sort methods (those which involve the re-ordering of elements at least)
Procedure exchange (var a,b:integer);
{industry standard way of exchanging a and b's values}
var t : integer;
begin
t:= a; a:=b; b:=t
end;
Using the above Exchange routine, and an organised algorithm,
it is possible to arrange elements in an array into a pre-determined
order (either ascending or descending)
Basic Bubble sort:
The algorithm:
starting at the first data item,
for each pass through the data (receding by 1 each pass)
compare successive pairs of values
if the items are in the wrong order
then swap them
else move to the next pair
A possible implementation...
Type vector = array[1..num] of integer
Procedure Bubblesort(var storage : vector);
{sorts an integer array into descending order}
var item, pass : 1..num;
begin
for pass := 1 to num-1 do
for item := 1 to (num-pass) do
if storage[item] < storage[item+1]
then exchange(storage[item],storage[item+1])
{else leave them alone}
end; {the 'bubbling'}
first 'pass' through the data 'bubbles' the largest to the far end
of the array, the next pass 'bubbles' the second largest to the second
last position and so on.
The bubble sort is very inefficient for large amounts of data
. Also it is very inefficient if data already partially sorted (4
items=6 ifs; 6 items=15 ifs; 10=45; 20=178; 40=780)
Basic Selection Sort:
The Algorithm
sequentially, looking at each data item,
if there are any elements to the left of current position that are larger
then exchange that value with biggest
otherwise move to the next data item
repeat above until the last item
A possible implementation
Procedure Selectionsort(var storage : vector);
{sorts an integer array into descending order}
var item, pass : 1..num;
begin
for pass := 1 to num do
for item := pass+1 to num do
if storage[item] > storage[pass]
then exchange(storage[item],storage[pass]);
{else you still have the biggest so far}
end;
The basis of this sort is that you are searching for the appropriate
value for each place in the sorted array in turn.
Basic Insertion Sort:
Much like a card player sorting a hand of cards: starting at the
left, if the next item is larger, then move the first into the seconds
place, and the second into the firsts place, then deal with the next
item, continually finding its place in the already sorted end by moving
smaller items out of the way
Procedure Insertionsort(var storage : vector);
{sorts an integer array into ascending order}
var pass : 1..num;
item : 0..num;
temp : integer;
begin
for pass := 2 to num do
begin
temp := storage[pass];
item := pass-1;
while (item> 0) and (temp > storage[item]) do
begin
storage[item+1] := storage[item];
dec(item);
end;
storage[item+1] := temp
end
end;
There are many types of sort, each of which has advantages and disadvantages
(in terms of flexibility, efficiency and readability). Most programmers
will have their own personal favourites.
The Basic Binary Search
This technique, also called a binary 'chop' is a highly efficient
search technique, that pre-supposes that the thing to be searched
is already arranged sequentially.
Question: is 11 in the array (array sorted)
Suppose 7 items in the list:
A possible implementation:
item :=11
left := 1; right := 7;
found := false;
while not found and (left <= right) do
begin
middle := (left+right) DIV 2;
if item > a[middle]
then left := middle + 1
else if item < a[middle]
then right := middle-1
else found := true
end;
if found then write('is in list')
else write('not found')
the basis of this search technique is the successive HALVING of the
search space - this leads very quickly to a result, and is highly
efficient (as opposed to searching through each element)
Sorting Tables
(remember, a table is an array of records)
Suppose we are dealing with a table containing information about
the army again:
index name rank serialnum
1 Parrts O Pt NCC1701
2 Adams D Lc HHG0042
3 Moncrieff G Lt HAL2001
Suppose the above table is how the data is stored.
Problem: print out a alphabetical list of soldiers.
Solution: obviously, we cannot step sequentially through the table
as they are not ordered ---> sort them first.
If we use any of the previously encountered sorting strategies, we
would end up physically exchanging the positions of data items (many
times) to achieve a list in alphabetic order.
This is NEVER DONE!!
Another solution involves storing another field of information about
table. There is already an ordinal index that describes the order
the data is stored in the table. If we pass the table to a sorting
routine,along with a vector with the original order, but instead of
moving the rows in the table, we move JUST THE INDEX number in the
vector, we would end with the following:
index name rank serialnum
2 Parrts O Pt NCC1701
3 Adams D Lc HHG0042
1 Moncrieff G Lt HAL2001
..meaning that ROW two is the first alphabetically, next comes row
3, followed by row 1 ---> we have now an indirect way of ordering
the table contents, and havn't moved any of the data in the table.
It is possible, and sometimes desirable, to have multiple indexes
for tables (depending on how you want the data to be printed out
