Selection Sort
published
last modified
3kb
Selection sort is a sorting algorithm. It is one of the more inefficient sorting algorithms available. It takes in the worst case in time complexity.
How Does Selection Sort... Sort?
The idea behind selection sort is very simple. We iterate through our array and find the index of the smallest element. Once we pass through the array we swap the first value with current minimum value.
![](../images/posts/selection-sort/selection-sort.webp)
I like to think of it as a claw machine grabbing the minumum element at every iteration and placing it in position.
Now the first position is sorted. We do this for the rest of the elements (because the first element is now sorted). That's it.
It's easy to see why this is . For every element we have to iterate through the array times. Let's say we have an array of . Then we have to iterate:
Which by arithmetic progression we know to be:
In Big O analysis we can drop the constants and keep the dominant power, which in this case is , thus having a .
Implementation
Below is an implementation.
#include <iostream>
#include <vector>
using namespace std;
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
vector<int> selection_sort(vector<int> &nums) {
for (int i = 0; i < nums.size(); i++) {
int idx = i;
for (int j = i + 1; j < nums.size(); j++) {
if (nums[j] < nums[idx]) {
idx = j;
}
}
swap(nums[i], nums[idx]);
}
return nums;
}
void print_vector(const vector<int> &vec) {
for (auto num: vec) {
cout << num << " ";
}
cout << endl;
}
int main() {
vector<int> test = {4, 6, 2, 1, 7, 8, 10, -1, 3, 16};
print_vector(test);
selection_sort(test);
print_vector(test);
return 0;
}
Contact
If you have any comments or thoughts you can reach me at any of the places below.