## Sorting

### Everyone Loves a Good Sort

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;
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')
```

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
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
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

wonko@wonko.info