Well I'm onto the fourth file and I haven't started sorting yet. If you're still here, then you've got more staying power than I have! Now onto the first sorting routine. ( Yaaaaaaayy! )
The simplest, most intuitive and in some ways the most important sorting routine is called the BUBBLE sort. ( For reasons that will become obvious later. ) It is important that you understand this routine because it is the most obvious, and logical of all sorting routines.
Let's start with a small group of numbers in a random order. E.G.
3 9 6 7 1
Put simply the routine works by repeately comparing adjacent numbers, and exchanging them if they are in the wrong order.
Firstly the top two numbers are compared, and if they are in the wrong order then they are swapped around. Then routine moves down the list by one number and the process is repeated. The process continues until the end of the list. The whole process is then repeated over and over until the routine has been through the entire list comparing adjacent numbers, and hasn't had to swap any pair aroud.
Say I want to arrange the above numbers into descending order using the bubble sort. First thing to do is compare the top two numbers, the first is a 3 and the second, a 9. Since I want the list in descending order, these two are in the wrong order and are swapped. The list now reads :
9 3 6 7 1
O.K. moving one down the list to the second number I have a 3 ( The one that has just been moved down. ), and a 7. They're in the wrong order so are swapped. And we have :
9 6 3 7 1
Moving down one again I have 3 and 7, again in the wrong order, so they are swapped to give :
9 6 7 3 1
Comparing the 3 and the 1, we find that for the first time that they are already in the right order. Also we have just compared the last two numbers in the list. Since we have swapped at least one pair of numbers during the routine, we have to go through the same process again.
Starting with the first two numbers we have a 9 and a 6 in the right order, so we move on. Next there are a 6 and a 7 in reverse order, so they are swapped, giving :
9 7 6 3 1
There will be no more swaps during this cycle since all the numbers are in the right order. But since SOME numbers were swapped around the routine is called again. On the next pass however, since the list is in the correct order none of the numbers are swapped around. The routine then recognises that the list isin order since it dosen't have to swap any numbers.
You may ask why the routine was called once more when we could see that the list was obviously sorted by the end of the second pass. The reason for this is that sorting routines usually work with much larger lists of numbers, and it is not so obvious when the list becomes finally sorted during a pass. But if a pass of the routine is completed without a single pair of numbers being swapped then it MUST be in order.
The file B.BUBBLE on the disk is a basic program that sets up an array of random numbers ( A%(size%) ) and then sorts them using a bubbe sort routine. The program prints out the numbers in their current order after each pass of the routine, so that you can see how each pass affects the order of the numbers.