Selection sort

Selection sort

            Let A be an array of n elements A[1], A[2], …., A[n]. Our aim is to sort the numbers in the array in ascending order. The steps are as follows

1)      Find the smallest element position in the list A[1], A[2], …., A[n] say k₁ and interchange the values A[1] and A[k₁]

2)      Find the smallest element position in the list A[2], A[3], ….., A[n] say k₂ and interchange the values A[2] and A[k₂].

3)      Find the smallest element position in the list A[3], A[4], ….., A[n] say k₃ and then interchange the values A[3] and A[k₃]

4)      Find the smallest element position in the list A[n-1] and A[n] say k_n-1 and then interchange the values A[n] and A[k_n-1].

Example -        Sort the array A using selection sort

                        A = (43, 72, 10, 23, 80, 1, 75)

           

Step    A[1]    A[2]     A[3]    A[4]    A[5]    A[6]    A[7]    POS

1           43       72         10        23       80        1         75        6               1        72         10        23       80       43        75    interchange A[1] & A[6] 2            1        72         10        23       80       43        75         3               1        10         72        23       80       43        75    interchange A[2] & A[3] 3            1        10         72        23       80       43        75         4               1        10         23        72       80       43        75    interchange A[3] & A[4] 4            1        10         23        72       80       43        75         6               1        10         23        43       80       72        75    interchange A[4] & A[6] 5            1        10         23        43       80       72        75         6               1        10         23        43       72       80        75   interchange A[5] & A[6] 6            1        10         23        43       72       80        75          7               1        10         23        43       72       75        80   interchange A[6] & A[7]                                    Sorted List

Procedure

            selection(A, N)

            {

                        for i = 1 to n do

            {

                        min = A[i] ;

                        k = i ;

                        for j = i + 1 to n do

                          if (min > A[j]) then

            {

                        min = A[j] ;

                        k = j ;

            }

                        A[k] = A[i] ;

                        A[i] = min ;

            }

            }

Complexity

            Let f(n) be the number of comparison required. Then

            F(n) = (n-1) + (n-2) + …….. + 1