Another way to sort a list by exchanging outoforder keys is

Another way to sort a list by exchanging out-of-order keys is called Bubble Sort.    Bubble Sort scans adjacent pairs of records and exchanged those found to have out-of-order keys. After the first time though the list, the record with the largest key is moved to its proper position. This process is done repeatedly on the remaining, unsorted part of the list until the list is completely sorted. Write the Bubble Sort algorithm. Analyze your algorithm, and show the result using order notation. Compare with the performance of the Bubble Sort Algorithm against those of Insertion Sort, Exchange Sort, and Selection Sort.

Solution

Bubble sort algorithm :

begin BubbleSort(arrlist)
for all elements of arrlist
if arrlist[i] > arrlist[i+1]
swap(arrlist[i], arrlist[i+1])
end if
end for
return arrlist
end BubbleSort

Best case complexities:

a) Bubble sort: O(n)

b) Insertion sort: O(n)

c) Selection sort: O(n^2)

Worst case complexitites:

a) Bubble sort: O(n^2)

b) Insertion sort: O(n^2)

c) Selection sort: O(n^2)