| ★ APPLICATIONS ★ DIVERS ★ SELECTION SORT (COMPUTING WITH THE AMSTRAD) ★ |
LET'S SORT IT ALL OUT... (Computing with the Amstrad) | Bubble quickly or shell out? (Computing with the Amstrad) |
SIMON MONK and SUE BRADSHAW begin a two-part article on sorting data in Basic A COMPUTER program, be it a word processor, database, or game, is about processing data. Often a vital part of the processing is sorting the data into order, and this was one of the first tasks to which computers were put in their early days. Sorting by computer is well understood, and many methods - or algorithms - have been developed. The majority are refinements of older techniques, but five fundamental types have emerged which have been around for some time now. It is unlikely that any more will be developed in the near future, unless they appear riding on the back of technological advances like parallel processing as found in the transputer. We will be showing you how these sorting techniques can be used on your CPC, and how to decide on one for particular circumstances. Even if you have no immediate use for sorting, you should find this an interesting avenue for exploration if you're just getting to grips with Basic The choice of sorting method depends on three things:
Accompanying this article are examples in Basic of the main sorting algorithms. We have tried to make them as general purpose as possible so they can be used in your own programs without too much modification. If the sort needs to be written in another language, first go through the algorithms by hand and make sure you understand what they are doing. In this connection we find a pack of cards very useful or, if you like, cut up squares of paper and write a number on each. You can then move them around to follow what is going on. The examples all assume integers are being sorted into ascending order. To sort strings, change the array to an array of strings, and any variables used to hold an element of the array into string variables. Altering the routines to sort in descending order is not difficult if you can follow how the algorithm works. To use the programs, first load the test program - Program I - and then merge the sorting routine of your choice. CPC464 owners with disc drives should save the modules as Ascii (use the ,a save option) to avoid a bug in the disc operating system rearing its head. The test program should be self-explanatory once you run it. It generates a list of random numbers, puts them in the array a, and sorts them into order using the chosen method. One point worth mentioning is that you'll be asked for a random number seed. If you specify the same one with different algorithms, you will get the same list of random numbers. This means you can do valid time comparisons, because the amount of sorting required will be the same in each case. With different seeds you'll get different lists of random numbers which may be more (or less) out of order, and therefore not be a fair contest. Selection sort This is a very widely-used method. It is quick for a small number of items, easy to program, and easy to understand. This algorithm sorts the data from the left and keeps a marker to show where the sorted part of the data stops and the unsorted part starts. 1: The unsorted marker is put at the first item of data. 2: The smallest number in the unsorted section is found and exchanged with the first number in the unsorted section. 3: The unsorted marker is moved one step to the right so that it now points to what was the smallest number in the unsorted section. 4: Repeat steps two to four until the unsorted marker points to the last number. Here's an example: 10 3 8 5 9 6 10 is the first unsorted number, so swap it with the smallest unsorted number which is 3. Then move the marker right one: 3 10 8 5 9 6 Now 5 is the smallest unsorted number so swap it with the first unsorted which is 10. Move the marker right one: 3 5 8 10 9 6 Next swap 6 with 8: 3 5 6 10 9 8 Now 8 with 10: 3 5 6 8 9 10 Now the smallest number in the unsorted section is 9, which is also the first number in the unsorted section. So we swap 9 with 9 which is a bit silly but perfectly possible. We therefore end up with: 3 5 6 8 9 10 Program II is an implementation of the selection sort algorithm. Just merge it with the test program and you'll be able to see it in action. To help you see how it relates to the description. Table I lists the variables used and their functions.
Insertion Sort This algorithm has the advantage of working more quickly if the data is already partly in order. It is more difficult to program than selection sort, but is quicker even if the data is random. Like selection sort, the insertion method keeps a marker to show where the unsorted part of the data starts, and works from left to right. 1: The smallest number in the data set is swapped with the first number. This is done only once. An example: 10 3 8 5 9 6 10 is swapped with the smallest number (3), and the unsorted marker is placed at the second number: 3 10 8 5 9 6 10 is inserted in its correct position in the sorted section, which does not involve its moving. However the marker must be moved: 3 10 8 5 9 6 Now it is the turn of 8 to be inserted. It goes between 3 and 10 so after the marker has been moved we get: 3 8 10 5 9 6 Next 5 is inserted between 3 and 8: 3 5 8 10 9 6 Now 9 is inserted between 8 and 10: 3 5 8 9 10 6 Finally 6 is inserted between 5 and 8: 3 5 6 8 9 10
Marks the edge of the unsorted region. Program III is the subroutine to merge with Program I for a demonstration, and Table II lists the variables used.
CWTA | ||||||||||||
|  |
|
