Selection Sort
Tobi here.
Sorting is one of the most fundamental things we do; not just in programming, but in life. Think about it: you sort your chores by priority, arrange books by size, group cutlery by type, people according to height. Sorting is everywhere.
In computing, it’s no different. Whether in finance, engineering, or data science, sorting is always involved. Whenever there’s data, there’s a need to organize it- to make it meaningful.
That’s why sorting is considered one of the foundational problems in computer science.
Among the many sorting algorithms, one of the simplest and most intuitive is Selection Sort. It’s not the most efficient, but it’s excellent for understanding how sorting logic works at a low level.
But before diving into how Selection Sort works, there’s one key concept we need to understand: Big O Notation.
Understanding Big O Notation
Big O describes how the time or space (memory) requirements of an algorithm grow as the input size increases.
For example:
O(1) means the algorithm takes the same amount of time regardless of the input size. It’s called constant time. But this doesn’t mean 1 second or 1 millisecond. It just means that no matter how large the data structure is, the time the algorithm takes to run doesn’t grow.
O(n) means time grows linearly with the input, like the simple search algorithm
O(n²) means time grows quadratically typical for basic sorting algorithms like Selection Sort in this case.
O(log n) e.g in the case of binary search . Instead of scanning every element (like linear search, O(n)), binary search cuts the search space in half with every step. That’s where the logarithm comes from.
O(n log n), means that the algorithm must handle every element (that’s the n) but does so in a way that divides the problem repeatedly (that’s the log n)
How Selection Sort Works
Selection Sort works by repeatedly finding the smallest element (looping) in a list and moving it to the front until the whole list is sorted.
Imagine you have a messy row of books, and you want to arrange them from smallest to largest.
You would do this:
Look through all the books and find the smallest one.
Move that smallest one to the first position.
Then, look through the remaining books again, find the next smallest one and place it next.
Keep doing that until everything is in order.
That’s exactly what Selection Sort does- it keeps selecting the smallest element one at a time and builds the sorted list step by step.
Algorithm Steps
Input: An array of n elements
Output: The array sorted in ascending order
Step 1:
Start from the first element in the array (index i = 0).
Step 2:
Initialize the current element arr[i] as the smallest.
Step 3:
Search through the rest of the array (j = i+1 to n-1)
If you find an element smaller than arr[i], mark its index as the new smallest.
Step 4:
After scanning the entire unsorted portion, swap the smallest element with the current element at i.
Step 5:
Move to the next position (i = i + 1) and repeat Steps 2–4 until the array is sorted.
In conclusion, Selection sort runs in O(n²) time because for each element, the algorithm has to look through the rest of the list to find the smallest.
Code implementation: click here!
Further reading: Grokking Algorithms- Aditya Bhargava
