Selection Sort

Hey Everyone !
In this article i am going to describe the Selection Sort Algorithm which has a complexity of O(n^2) and people don't prefer to use this algorithm in competitve programming contests, but i am writing this because it can be asked in viva or during exams in colleges.

---

What is Selection Sort?
Selection sort is just a sorting algorithm which sorts the given array in the ascending order order by selecting the minimum element(say M) from the array, and then selecting the next minimum element(say P) from the array and this time not considering the last minimum element(ignoring M this time)and this goes on until the whole array elements are covered by continuously ignoring the previous minimum elements. Similarly we can sort the array in reverse order by selcting the maximum element everytime instead of minimum. Lets have a look at the procedure. Observe how we are ignoring the previously selected minimum elements by using a variable start and method swap().
Procedure:
Note: Consider 0-based indexing of array elements!

1. Let start = 0 and end = n where n is the size of the array.
2. Find the minimum element in the array from start to end.
3. Swap this minimum element with the element at the index represented by value of variable start.
4. Increment start by 1.
5. Repeat the procedure from step 2 to step 4 until (start != end).
6. Thats it !

---

Example
let n = 5, Array a[ ] = {4, 2, 6, 3, 1}
start = 0 and end = 4
Minimum element from index 0 to 4 is 1. So swap 1 with 4.
a[ ] = {1, 2, 6, 3, 4} and start = 0 + 1 = 1
Minimum element from index 1 to 4 is 2. So swap 2 with 2.
a[ ] = {1, 2, 6, 3, 4} and start = 1 + 1 = 2
Minimum element from index 2 to 4 is 3. So swap 3 with 6.
a[ ] = {1, 2, 3, 6, 4} and start = 2 + 1 = 3
Minimum element from index 3 to 4 is 4. So swap 4 with 6.
a[ ] = {1, 2, 3, 4, 6} and start = 3 + 1 = 4
Minimum element from index 4 to 4 is 6. So swap 6 with 6.
a[ ] = {1, 2, 3, 4, 6} and start = 4 + 1 = 5
Now start becomes equal to n, so we stop at this point.

Implementation in C++

#include<bits/stdc++.h>

using namespace std;

void SelectionSort(int *a, int n){
    int start = 0;
    int end = n;
    while(start != end){
        int mini = INT_MAX, idx = start;
        for(int i = start ; i < end; i ++){
            if(mini > a[i]){
                mini = a[i];
                idx = i;
            }
        }
        swap(a[start], a[idx]);
        start++;
    }
}

int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i = 0 ; i < n ; i ++) {
         cin >> a[i];
    }
    SelectionSort(a, n);
    cout << "After Sorting:\n";
    for(int i = 0 ; i < n ; i++){
        cout << a[i] << " ";
    }
}

---

Complexity: Time Complexity is clearly O(n^2). We used 2 nested loops and outer loop runs from 0 to n and inner loop runs from start to n where variable start increments by 1 in every step.
Let counter = 0 (initially).
initially start = 0, so inner loop runs from 0 to n. Counter = n
now start = 1, so inner loop runs from 1 to n. Counter = n + (n - 1)
....
....
....
now start = n - 1, so inner loop runs from (n - 1) to n. Counter = n + (n - 1) + . . . . + 1.
So Counter = n * ( n + 1 ) / 2.
Hence complexity is O(n^2).
Refer CLRS to know more abot complexity of algorithms.

---

Thank You for reading this post !