Selection Sort - Cplusplus

In Selection Sort algorithm, First, find the smallest element and swap it with the first. Sort the rest of the list the same way.

Selection Sort

Algorithm :

for i in 0 .. n-2
    small := i
    for j in i+1 .. n-1
        if (a[j] < a[small]) small := j
    swap(a[i], a[small])

Example :

30 64 26 46 109 21 84 98
21 64 26 46 109 30 84 98
21 26 64 46 109 30 84 98
21 26 30 46 109 64 84 98
21 26 30 46 64 109 84 98
21 26 30 46 64 109 84 98
21 26 30 46 64 84 109 98
21 26 30 46 64 84 98 109

Notes :

It has O(N^2) time complexity in all cases.
It has minimum number of swapping in worst case, i.e., O(N) time.
After pass k, the first k elements are in their final absolute positions.
It, it does not require extra space, so in-place sorting.
Selection sort is NOT a stable sorting algorithm, but can be modify as stable sorting technique.

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.