Data Structures - Selection Sort

Basic programming - Selection Sort

Approach:

Declare two variables, i likes the end pointer of sorted vector and j likes the scanning pointer.

Aims to find the smallest value (or biggest value), therefore, j starts from i to scan until the end of nums. Then, the smallest value is changed with the value of index i by calling swap(). It means adding the smallest value to the sorted vector. Next step, i moves to the next index and go back to the previous action until all values are sorted.

Time complexity:

Best Case：Ο(n²)

Worst Case：Ο(n²)

Average Case：Ο(n²)

P.S. Whatever the input is, there are two for-loop to run!

Space complexity: O(1)

Stable/Unstable: Unstable

Source code

Version 1

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void swap(int& l, int& r){
    int temp = l;
    l = r;
    r = temp;
}

vector<int> selectSort(vector<int>& nums){
    const int n = nums.size();
    for(int i = 0; i < n; i++){
        int min_value = INT_MAX;
        int pos = 0;
        for(int j = i; j < n; j++){
            if(nums[j] < min_value){
                min_value = nums[j];
                pos = j;
            }
        }
        if(pos != i){
            swap(nums[i], nums[pos]);
        }
    }
    return nums;
};

int main()
{   
    vector<int> input{51,96,6,68,36,27,55,6,56,16};
    vector<int> sortedAns = selectSort(input);
    
    for(int i = 0; i < sortedAns.size(); i++){
        cout << sortedAns[i] << " ";
    }
    
    return 0;
}