Sorting is one of the most important operations performed by computers. In the days of magnetic tape storage before modern data-bases, it was almost certainly the most common operation performed by computers as most "database" updating was done by sorting transactions and merging them with a master file. It's still important for presentation of data extracted from databases: most people prefer to get reports sorted into some relevant order before wading through pages of data!
There are a large number of variations of one basic strategy for sorting. It's the same strategy that you use for sorting your bridge hand. You pick up a card, start at the beginning of your hand and find the place to insert the new card, insert it and move all the others up one place.
| Insertion Sort Animation This animation was written by Woi Ang. Insertion Sort.zip |
In quicksort, we divide the array of items to be sorted into two partitions and then call the quicksort procedure recursively to sort the two partitions, ie we divide the problem into two smaller ones and conquer by solving the smaller ones. The first algorithm is not an in place sort but uses an auxillary array. The second algorithm performs the sort using only the input array - in place sort.
| QuickSort Animation 1 This animation was based on a suggestion made by Jeff Rohl; it was written by Woi Ang. QuickSort.zip |
| QuickSort Animation 2 This animation uses the partition in place approach; it was written by Chien Wei Tan QuickSort2.zip |
This sort assumes that there are n distinct keys in the range 0 .. n-1. In addition to this restriction, it uses auxillary arrays for the sort, so that this version trades space for time.
The bin sorting strategy may appear rather limited, but it can be generalized into a strategy known as Radix sorting
| Bin Sort
Animation This animation was written by Woi Ang. Bin Sort.zip |
| Radix Sort Animation This animation was written by Woi Ang. Radix Sort.zip |
In the following animation, note that both the array representation (used in the implementation of the algorithm) and the (logical) tree representation are shown. This is to demonstrate how the tree is restructured to make a heap again after every insertion or deletion.
|
Priority Queue Animation This animation was written by Woi Ang. Priority Queue.zip |
We noted earlier, when discussing heaps, that, as well as their use in priority queues, they provide a means of sorting:
| Heap Sort Animation This animation was written by Woi Ang. Heap Sort.zip |
In the small number of cases, where multiple keys map to the same integer, then elements with different keys may be stored in the same "slot" of the hash table. It is clear that when the hash function is used to locate a potential match, it will be necessary to compare the key of that element with the search key. But there may be more than one element which should be stored in a single slot of the table. Various techniques are used to manage this problem:
The following animation explores several of these strategies.
| Hash
Table Animation This animation was written by Woi Ang. Hash Table.zip |
A red-black tree is a binary search tree with one extra attribute for each node: the colour, which is either red or black. We also need to keep track of the parent of each node. RB trees remain balanced - and thus guarantee O(logn) search times - in a dynamic environment. Or more importantly, since any RB tree can be re-balanced - but at considerable cost - in O(logn) time.
| Red-Black Tree Animation This animation was written by Linda Luo, Mervyn Ng and Woi Ang. Red Black Tree.zip |
Dynamic problems obtain their efficiency by solving and storing the answers to small problems. Thus they usually trade space for increased speed.
| Optimal Binary Search Tree Animation This animation was written by John Morris and (mostly) Woi Ang OBS Tree.zip |
The cost of multiplying an nxm by an mxp one is O(nmp) (or O(n3) for two nxn ones). A poor choice of parenthesization can be expensive.
| Matrix Chain Multiplication This animation was written by Woi L. Ang Matrix Chain Mult.zip |
Suppose we have a group of islands that we wish to link with bridges so that it is possible to travel from one island to any other in the group. Further suppose that (as usual) our government wishes to spend the absolute minimum amount on this project (because other factors like the cost of using, maintaining, etc, these bridges will probably be the responsibility of some future government). The engineers are able to produce a cost for a bridge linking each possible pair of islands. The set of bridges which will enable one to travel from any island to any other at minimum capital cost to the government is the minimum spanning tree.
| Minimum Spanning Tree Animation This animation was written by Mervyn Ng. Minimum Spanning Tree.zip |
In this animation, a number of cases have been selected to show all aspects of the operation of Dijkstra's algorithm. Start by selecting the data set (or you can just work through the first one - which appears by default). Then select either step or run to execute the algorithm. Note that it starts by assigning a weight of infinity to all nodes, and then selecting a source and assigning a weight of zero to it. As nodes are added to the set for which shortest paths are known, their colour is changed to red. When a node is selected, the weights of its neighbours are relaxed .. nodes turn green and flash as they are being relaxed. Once all nodes are relaxed, their predecessors are updated, arcs are turned green when this happens. The cycle of selection, weight relaxation and predecessor update repeats itself until all the shortest path to all nodes has been found.
|
Dijkstra's Algorithm Animation This animation was written by Mervyn Ng and Woi Ang. |