The selection sort enhances the bubble sort by making only a single swap for each pass through the rundown. Indorder to do this, a selection sort searches for the biggest value as it makes a pass and, after finishing the pass, places it in the best possible area. Similarly as with a bubble sort, after the first pass, the biggest item is in the right place. After the second pass, the following biggest is set up. This procedure proceeds and requires n-1 goes to sort n item, since the last item must be set up after the (n-1) st pass.

ALGORITHM: SELECTION SORT (A)
1. k ← length [A]
2. for j ←1 to n-1
3. smallest ←  j
4. for I ← j + 1 to k
5. if A [i] < A [ smallest]
6. then smallest ←  i
7. exchange (A [j], A [smallest])

Analysis:

1. Input: n elements are given.
2. Output: the number of comparisons required to make sorting.
3. Logic: If we have n elements in selection sort, then n-1 passes are required to find a sorted array.

 In pass 1: n-1 comparisons are required
 In pass 2:  n-2 comparisons are required
 In pass 3: n-3 comparisons are required
............................................................................
...............................................................................
 In pass n-1: 1 comparison is required 
 Total comparisons: T (n) = (n-1) + (n-2) + (n-3) +........+ 1
                          = 

= o (n

2)
	Therefore complexity is of order n2 

Example:

Sort the following array using selection sort: A [] = (7, 4, 3, 6, 5).

A [] =

74365

1 Iteration:

1. Smallest =7  
2.       4 < 7, smallest = 4  
3.       3 < 4, smallest = 3  
4.    6 > 3, smallest = 3  
5.    5 > 3, smallest = 3  

Swap 7 and 3

34765

2^nd iteration:

1. Smallest = 4  
2. 4 < 7, smallest = 4  
3. 4 < 6, smallest = 4  
4. 4 < 5, smallest = 4  

No Swap

34765

3^rd iteration:

1. Smallest = 7  
2. 6 < 7, smallest = 6  
3. 5 < 7, smallest = 5  

Swap 7 and 5

34567

4^th iteration:

1. Smallest = 6  
2. 6< 7, smallest = 6  

No Swap

34567

Finally, the sorted list is:

34567