The bubble sort was invented in the early days of computing. To understand how a bubble sort works, imagine that you have a list of ten names to sort into alphabetical order. The bubble sort algorithm begins by comparing names nine and ten and putting just those two names into proper order. If ten comes before nine alphabetically, the names are switched (nine goes into the place previously occupied by ten and vice-versa.) Otherwise, the names are not switched.
Then the algorithm compares names eight and nine, switching them if necessary, and so on until it reaches the top of the list.
Note that, somewhere along the line, the algorithm gets to the name that should be at the top of the sorted list and then swaps it with every name in the list above it until it actually is at the top. After one time through the list, the first name is in its proper location but the second name probably is not.
Imagine, for example, that before the program begins sorting, Aaron A. Aardvark happens to be the tenth name on the list and Abigail Abacus happens to be ninth. The algorithm compares them and switches them. Mr Aardvark is now number nine, and he continues to be compared and switched until he becomes number one. But even though Ms Abacus should be number two in the list, she becomes number ten after the switch and she is not compared again on this pass through the list.
When the algorithm begins the scond pass through the list, then, you can be sure that the name that should be first already is first but you cannot say anything about the location of the second name.
At some point in the second pass, however, the algorithm comes across the name that should be second and, now that the first name is out of the way, it keeps comparing and switching that name until it reaches its proper second place in the list. After two times through the list, then, you can be sure that the first two names are both in their proper places.
Likewise, after going through the list a third time, you can be sure that the third name is in its proper third place. After going through the list a number of times that is equal to the number of names on the list, you can be sure that all the names are in their proper places.
This algorithm is called the bubble sort because names rise to the top one at a time, much like air bubbling up through water.
The bubble sort could be made more efficient in several ways.
For example, it could include a flag to let the program know the sorting is complete if the sort goes through the entire list without changing the place of any record. If only one name has been added since the last time you sorted, the sort program has to go through the list only once to put it in its proper place. The second time through the list, the program would find that it does not have to change the order of any records, proving that all of the records are already in the right order. At this point, the sort could simply terminate, rather than going through the list again and again, and not making any changes, until it has made a number of passes equal to the number of records in the list.
In addition, you could cut sorting time in half by not comparing the records that are already properly sorted. Instead of comparing all of the names each time through, the program could omit the first name on the second pass through the list, the first two names on the third pass through the list, and so on.
In fact, the last pass through the list can be omitted entirely. If all of the names except the last one are known to be in the proper order, then obviously all the names are in the proper order. This improvement is particularly easy to implement since you just go through the list one less time than the number of names in the list. (If you have a list of ten names, you go through the list nine times.)
It is not worthwhile to work too hard on improving the efficiency of this algorithm, however. There are other sorting algorithms that are far more efficient. The bubble sort was popular on mainframe computers that were programmed during the day and were left running all night to process their data. Its main virtue was simplicity rather than speed.
The bubble sort program should do the following:
Strong Hint: Since the specification tells you exactly how many names will be entered, you might want to consider storing the names in an array.