Selection Sort (concept & algorithm)

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.

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 )

---

C program : selection-sort-c program