IPT - A Virtual Approach IPT A Virtual Approach by Peter Whitehouse
Quick Links:
 
 
Information and Intelligent Systems Social and Ethical Implications Human Computer Interaction Software and Systems Engineering eXercise Files Course Outline and Assessment A-Z of Geeky Acronyms Terrace Work Program 2004 Sillybus FAQ = Frequently Asked Questions Help
 
 

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

 

 

wonko@wonko.info
©Copyright t 1992..2017+. Edition 25.150117
wonkosite
Creative Commons License
This work is licensed under a
Creative Commons Attribution-NonCommercial-ShareAlike 2.1 Australia License
.