Bubble SortThe Bubble Sort compares

Bubble Sort
The Bubble Sort compares each successive pair of elements in an un-ordered 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
o First (5) and second (4) elements compared. 4 less than 5 therefore elements inverted.
" Current list: 4,5,9,7,2,8
o Second (now 5) and third (9) elements compared. In correct order so no change.
" Current list: 4,5,9,7,2,8
o 9 and 7 compared and inverted
" Current list: 4,5,7,9,2,8
o 9 and 2 compared and inverted
" Current list: 4,5,7,2,9,8
o 9 and 8 compared and inverted
" Current list: 4,5,7,2,8,9
" Pass 2
o Same method used in Pass 1 applied to current list (4,5,7,2,8,9)
o Resultant list: 4,5,2,7,8,9
" Pass 3
o Resultant list: 4,2,5,7,8,9
" Pass 4
o Resultant list: 2,4,5,7,8,9
" Pass 5
o 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 n-1 elements (where n is the number of elements in the original list). Pass 3 only needs to deal with n-2 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 n-1. 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.
There are many different types of sorts that can be carried out both in the real world and computationally. One common type of sort is the Selection Sort. The Selection sort algorithm iterates over the values in an unordered list successively moving the lowest value to the front of the list. Each time an element is moved to the head of the list (or array) this is ignored by the following iterations. On the next iteration, the lowest value is then moved to the position in the list after the previous lowest value.