CONCEPT OF SELECTION SORT - DATA STRUCTURE

Algorithm for Selection Sort :

ALGORITHM    : Selection sort ( A , N )

                              A is an array with N elements 

STEP 1   : FOR I = 0 TO N - 2 DO

STEP 2   : FOR J = I + 1 TO N - 1 DO

STEP 3   : IF A [ I ] > A [ J ]

STEP 3.1 : TEMP = A [ I ]

STEP 3.2 :  A [ I ]   =  A [ J ]

STEP 3.3 : A [ J ] = TEMP

STEP 4    : END IF

STEP 5    : J = J + 1  GOTO STEP 2  (OR) NEXT J

STEP 6    : NEXT I

STEP 7    : END

Procedure / Function of Selection Sort in C

void SelectionSort ( int a [ 50 ], int n)

{

    int i, j, temp ;

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

    {

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

        {

              if a [ i ] > a [ j ]

                 {

                       temp = a [ i ] ;

                      a [ i ] = a [ j ] ;

                      a [ j ] = temp ;

                }

        }

    }

}

EVALUATION OF SELECTION SORT :

 

To sort array of ( n ) element , selection sort needs ( n - 1 ) passes (Comparison)

PASS                                NO. OF COMPARISON

    1                                                    N -1

    2                                                    N -2

    3                                                    N -3

    4                                                    N -4

    -                                                        -

    -                                                        -

 N -1                                                     1

------------------------------------------------------------------------

TOTAL                                  1 + 2 + 3 + 4 + ----

------------------------------------------------------------------------

            Fn = n( n -1 ) / 2   ( This show number of comparison)

Note :

Comparison operators takes same time according to time complexity.

Such as : { < , <= , > , >= , == , != } take same time.

 There are two type of view of thinking .

1. Optimistic view.

2. Pessimistic view

In Optimistic view we always think positively.

In Pessimistic  view we always think negatively.

O → This symbol is called Big O notation.

Big O notation show the rate of growth.

O of constant = 1

Example: 

There are two type of cases:

1. Worst performance case

2. Best performance case or sophisticated