Suppose an array A with N elements is in memory. Selection sort works as follows

First find the smallest element in the list and put it in the first position. Then, find the second smallest element in the list and put it in the second position and so on.

First find the smallest element in the list and put it in the first position. Then, find the second smallest element in the list and put it in the second position and so on.

Pass 1: Find the location LOC of the smallest element in the list A[1], A[2], … A[N]. Then interchange A[LOC] and A[1]. Then: A[1] is sorted

Pass 2: Find the location LOC of the smallest element in the sublist A[2], A[3], … A[N]. Then interchange A[LOC] and A[2]. Then: A[1],A[2] is sorted since A[1] <= A[2].

Pass 3: Find the location LOC of the smallest element in the sublist A[3], A[4], … A[N]. Then interchange A[LOC] and A[3]. Then: A[1], A[2],A[3] is sorted, since A[2] <= A[3].

Pass
N-1: Find the location LOC of the
smallest element in the sublist
A[N-1], A[N]. Then interchange A[LOC] and A[N-1]. Then: A[1], A[2], ….. ,
A[N] is sorted, since A[N-1] <= A[N].

A
is sorted after N-1 pass.

### Example :

selection sort example (read algo than follow steps) |

#### Complexity :

f(n)
= (n-1) + (n-2) + …… + 2+ 1 = n(n-1)/2 = O(n2 )

## No comments:

## Post a Comment

THANKS FOR UR GREAT COMMENT