
Notes > Computation and Algorithms > Bubble Sort and Sorting

The Bubble Sort compares each successive pair of elements in an unordered list and inverts the elements if they are not in order. The following example illustrates the bubble sort.
The list "5,4,9,7,2,8" needs to be sorted from lowest to highest. The following steps are carried out:
 Pass 1
 First (5) and second (4) elements compared. 4 less than 5 therefore elements inverted.
 Current list: 4,5,9,7,2,8
 Second (now 5) and third (9) elements compared. In correct order so no change.
 Current list: 4,5,9,7,2,8
 9 and 7 compared and inverted
 Current list: 4,5,7,9,2,8
 9 and 2 compared and inverted
 Current list: 4,5,7,2,9,8
 9 and 8 compared and inverted
 Current list: 4,5,7,2,8,9
 Pass 2
 Same method used in Pass 1 applied to current list (4,5,7,2,8,9)
 Resultant list: 4,5,2,7,8,9
 Pass 3
 Resultant list: 4,2,5,7,8,9
 Pass 4
 Resultant list: 2,4,5,7,8,9
 Pass 5
 No changes would be made in this pass therefore the algorithm has reached its termination point and the list is sorted
It is worth noting that at the end of Pass 1 the largest element (9) has been moved to the end of the list. Similarly, in Pass 2, the second largest element (8) has been moved to the second last position in the list and so on. This pattern always occurs in the Bubble Sort.
Related to this point, it is also noteworthy that Pass 2 only needs to deal with n1 elements (where n is the number of elements in the original list). Pass 3 only needs to deal with n2 and so on. This is because at the end of each pass, another element has been put in its correct position at the end of the list. This leaves one less element that needs to be sorted for the next pass.
Best and Worst Case Analysis
The worst case for the number of passes is n1. The best case is 1 pass which would occur if the list was already sorted. The list needs to be checked through at least once to check whether or not any inversions / swaps need to be done.
Search for "Bubble Sort" on:
Google 
Kelkoo 
Amazon 
eBay (UK) 
eBay (US)
Search for "Bubble Sort" on the rest of Computing Students: Bubble Sort


