The bubble sort gets its name from the way smaller entries "sink" to the bottom of the array during the sort while larger entries "bubble up" to the top. To carry out the bubble sort on the array shown in Figure 8.4(a), traverse the array, comparing two adjacent elements, starting with the first two, and ending with the last two. If the [i + 1]th element value exceeds the ith, interchange the two element values.When a traversal is completed, it is called a pass through the array. Continue making passes until a pass occurs in which no interchanges are required.
In the example, after pass 1, the array looks like Figure 8.4(b). Since at least one interchange was made, another pass is made, yielding Figure 8.4(c). Again, at least one interchange was made, so the program must make another pass.
Will this process continue forever making passes, or eventually stop? Clearly, once it stops since no interchanges were made on the last pass, the array is sorted. If any number were out of order, at least one interchange would have been made during that pass.
Notice that after the first pass the smallest entry, 3, was at the bottom of the array. After the second pass the two smallest entries, 10 and 3, were in order at the bottom of the array. This was not accidental. Notice that the two smallest entries will never be moved, and the third smallest element (13 in this case) will be encountered on the next pass. Once it is encountered, it will always be interchanged with the adjacent lower record to which it is compared. It will eventually come to rest just above the second smallest entry.
