Next:9.2 Insertion SortUp:9. Sorting MethodsPrevious:9. Sorting Methods

9.1 Bubble Sort

Let a[1], a[2],..., a[n] be n records to be sorted on a key field ``key''. In bubble sort, records with low keys (light records) bubble up to the top.


        for(i = 1;i < = n - 1;i + +)


                for(j = n;j > = i + 1;j - -)

                    if (a[j].key <a[j - 1].key)

                        swap the records a[j] and a[j - 1]



At the end of the (i - 1)st iteration, we have

$\displaystyle \underbrace{a[1] \space \ldots \space a[i-1]}_{\begin{array}{l}\mbox{sorted as in the}\\\mbox{final order}\end{array}}^{}\,$$\displaystyle \underbrace{a[i] \space \ldots \space a[n]}_{\begin{array}{l}\mbox{unsorted }\end{array}}^{}\,$
In the ith iteration, the ith lowest key bubbles up to the ithposition and we get
$\displaystyle \underbrace{a[1] \space \ldots \space a[i-1] a[i]}_{\begin{array}{l}\mbox{sorted}\end{array}}^{}\,$$\displaystyle \underbrace{a[i+1] \space \ldots \space a[n]}_{\begin{array}{l}\mbox{unsorted }\end{array}}^{}\,$
Worst case complexity and also average case complexity is O(n2).