9.3 Selection Sort

i^th Iteration

$$\underbrace{A[1] A[2] \space \cdots \space A[i-1]}_{\begin{array}{l}\mbox{sorted as in the}\\\mbox{final sequence}\end{array}}^{}\,$$$$\underbrace{A[i] \space \cdots \space A[n]}_{\begin{array}{l}\mb......lect least among these}\\\mbox{and swap with} \space \ A[i]\end{array}}^{}\,$$ $\Downarrow$ $$\underbrace{A[1] A[2] \space \cdots \space A[i]}_{\begin{array}{l}\mbox{sorted as in }\\\mbox{final sequence}\end{array}}^{}\,$$$$\underbrace{A[i+1] \space \cdots \space A[n]}_{\begin{array}{l}\mbox{yet to be sorted}\end{array}}^{}\,$$

    {

        for(i = 1, i$\leq$n - 1;i + +)

            {

                lowindex = i; lowkey = A[i] $\rightarrow$ key;

                for(j = i + 1;j$\leq$n;j + +)

                if (A[j] $\rightarrow$ key < lowkey)

                {

                    lowkey = A[j] $\rightarrow$ key;

                    lowindex = j

                }

           swap (A[i], A[lowindex])

        }

}

• Number of swaps = n - 1
• Number of comparisons = ${\frac{n(n-1)}{2}}$