Selection Sort in C++

        It is a sorting process in which the location is fixed and then value selected from the location is compared with the rest. Swapping values of two locations is carried out if need arises.

Suppose A is an array consisiting of 6 integers as shown

        A[0]= 2,    A[1]= 5,    A[2]= 8,    A[3]=11,    A[4]=14,   A[5]=18

This array has to be arranged in an ascending order using selection sort method. The step and comparison involved while arranging the array are listed below.

STEP 1

2  5  8  11  14  18                 2<5  so swap 2 and 5

5  2  8  11  14  18                 5<8  so swap 5 and 8

8  2  5  11  14  18                 8<11  so swap 8 and 11

11  2  5  8  14  18                 11<14  so swap 11 and 14

14  2  5  8  11  18                 14<18  so swap 14and 18

18  2  5  8  11  14

Now largest value is shifted to first position.

STEP 2

18  2  5  8  11  14                 2<5  so swap 2 and 5

18  5  2  8  11  14                 5<8  so swap 5 and 8

18  8  2  5  11  14                 8<11  so swap 8 and 11

18  11  2  5  8  14                 8<11  so swap 8 and 11

18  14  2  5  8  11                 11<14  so swap 11 and 14

 Now the second largest value is shifted to second position.

STEP 3

18  14  2  5  8  11                 2<5  so swap 2 and 5

18  14  5  2  8  11                 5<8  so swap 5 and 8

18  14  8  2  5  11                 8<11  so swap 8 and 11

18  14  11  2  5  8

Now the third largest value is shifted to third position.

STEP 4

18  14  11  2  5  8                 2<5  so swap 2 and 5

18  14  11  5  2  8                 5<8  so swap 5 and 8

18  14  11  8  2  5                

STEP 5

18  14  11  8  2  5                 2<5  so swap 2 and 5

18  14  11  8  5  2                

Step 1 uses 5 comparisons. Step 2 needs 4 comparisons and so on. The array A requires 5 steps where each step uses 6-step value comparisons. Therefore a list having n values needs n-1 steps with each step using n- step value comparison. So order is O(n²).

Algorithm:- Suppose that an array ‘A’ having n numbers has to be arranged in an descending order. The selection sort algorithm can be used to accomplish the same.

STEP 1:- Repeat step 2   for i=0 to n-2

STEP 2:- Repeat step 3   for j=i+1 to n-1

STEP 3:-  if (A[i] < A[j] )

                                swap A[j] and A[j+1]

                end of if;

                end of step 2;

    end of step 1;

STEP 4:- STOP

C++ Programme code

#include<iostream>

#include<iomanip.h>

void main()

{

     int a[50], n,i,j;

     cout<< “Enter the size of list ”;

     cin>>n;

     cout<< “Enter”<<n<< “values”;

     for(i=0; i<n; i++)

           cin>> a[i];

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

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

                if(a[i] < a[j])

                {

                     int t = a[i];

                     a[i] = a[j];

                     a[j] = t;

                 }

     cout<< “Arranged list is...”;

     for(i=0; i<n; i++)

           cout<< setw(5) << a[i];

}