Selection Sort

Saturday. June 05, 2021 - 1 min

programming-fundamentals sorting

Selection sort is a sorting algorithm that basically divides the list of elements into 2 subarrays - a sorted subarray and an unsorted subarray. Initially, the sorted array doesn't have any elements. It traverses the unsorted sub-array, picking the smallest element and putting it to the unsorted array. This continues until there are no more elements present in the unsorted subarray.

#include <iostream>
#include <vector>

using namespace std;

void SelectionSort(vector<int>& a)
{
    int min_index;
    int n = a.size();

    for(auto i=0;i<n-1;++i)
    {
        min_index = i;
        for(auto j =i; j<n;++j)
        {
            if(a[j]<a[min_index])
            {
                min_index = j;
            }
        }
        swap(a[i],a[min_index]);
    }
}

int main()
{
    vector<int> a{12, 8, 3, 7, 10, 8, 23, 5, 17};
    SelectionSort(a);
    for(auto x:a)
        cout<<x<<" ";
    return 0;
}

Time Complexity:

Worst Case	Average Case	Best Case
O(n²)	O(n²)	O(n²)

Space Complexity:

O(1)

Vidhatha Vivekananda

Programmer. Interested in nature and philosophy.