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:
1. Worst performance case
2. Best performance case or sophisticated
No comments:
Post a Comment