Selection Sort

Selection sort is a sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list. 

The smallest element is selected from the unsorted array and swapped with the leftmost element and it becomes part of sorted array. This process continues until all the elements are sorted.

This algorithm is not suitable for large data sets as its average and worst case complexities are of O(n²).

Ex:

14        33        27        10        35        19        42        44

Find the lowest value which is 10 and swap it with 14 which is left most value

10        33        27        14        35        19        42        44

For second position we find 14 is second lowest so it is swapped into second position

10        14        27        33        35        19        42        44

The same process is applied

10        14        19        33        35        27        42        44

 

10        14        19        27        35        33        42        44

 

10        14        19        27        33        35        42        44

Now the list is in sorted order.

Function Code:

void SelectionSort(int A[ ], int n)

{

int i, j;

int minpos, temp;

for(i = 0; i < n − 1; i++)

{

minpos = i;

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

//find the position of min element as minpos from i + 1 to n − 1

{

if(A[j] < A[minpos])

minpos = j;

}

if(minpos != i)

{

temp = A[i];

// swap the i^th element and minpos element

A[i] = A[minpos];

A[minpos] = temp;

}

}

}