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

$$\underbrace{a[1] \space \ldots \space a[i-1]}_{\begin{array}{l}\mbox{sorted as in the}\\\mbox{final order}\end{array}}^{}\,$$$$\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 $$\underbrace{a[1] \space \ldots \space a[i-1] a[i]}_{\begin{array}{l}\mbox{sorted}\end{array}}^{}\,$$$$\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(n²).