Implement the bubble sort algorithm.
The bubble sort is so called because it compares adjacent items, "bubbling" the smaller one up toward the beginning of the list. By comparing all pairs of adjacent items starting at the end of the list, the smallest item is guaranteed to reach the beginning of the list at the end of the first pass.
The second pass begins again at the end of the list, ultimately placing the second smallest item in the second position in the list. During the second pass, there is no need to compare the first and second items, since the smallest element is guaranteed to be in the first position.
Bubble sort takes at most n-1 passes for a list of n items. During the first pass, n-1 pairs need to be compared. During the second pass, n-2 pairs need to be compared. During the ith pass, n-i pairs need to be compared. During the last pass, n-(n-1) or one pair needs to be compared. If, during any pass, no two adjacent items need to be interchanged, the list is in order and the sort can terminate. If it continues, no further interchanges will occur.
Bubble sort sometimes is called interchange sort or exchange sort. A variation on the bubble sort starts each pass at the beginning of the list, interchanging items as needed so that a larger item "sinks" below a smaller item following each comparison. Such a sort might be called a "rock sort," but this term is not in common usage. Bubble sort is easily modified to put elements in descending order (with the largest element at the beginning of the list).