Interview Kickstart has enabled over 3500 engineers to uplevel.
If you are a software developer preparing for a technical interview, you’ve come to the right place! Most tech companies use data structure problems to test the coding prowess of software engineers. You should be well-versed not only with all data structure concepts, but also with the different methods of sorting data.
Selection sort is one such method that you must brush up on for your coding round. In this article, we cover:
By definition, selection sort is an in-place comparison-based sorting algorithm. This sorting algorithm is known for its simplicity and memory efficiency — it doesn’t take up any extra space. The selection sort method repeatedly searches “remaining items” to find the least one and moves it to its final location.
Let’s dive deeper into what this means.
This algorithm divides the input array into two subparts — the sorted part and the unsorted part. Initially, the sorted part of the array is empty, and the unsorted part is the input array.
The algorithm works on the principle of finding the lowest number from the unsorted part of the array and then swapping it with the first element of the unsorted part. This is done over and over until the entire array becomes sorted (in ascending order).
Consider the following example:
arr [ ]= 19 10 4 8 3
First, we search for the lowest number in arr[0-4] to swap it with the unsorted part’s first element. And so, we swap 3 with 19, and the array gets modified as follows:
arr[ ]= 3 10 4 8 19
Next, we need to find the lowest number in arr[1-4] to swap with the unsorted array’s first element. So, we swap 4 with 10.
arr[ ]= 3 4 10 8 19
Now, we must find the lowest number in arr[2-4] and swap.
arr[ ]= 3 4 8 10 19
Do the same for arr[3-4]
arr[ ]= 3 4 8 10 19
And our array is sorted!
Now that you know how selection sort works, following the algorithm steps will be pretty easy:
Once you understand the logic, writing the code for selection sort is pretty straightforward. Are you feeling confident yet?
Here’s the pseudocode to help you write the code in any language of your choice.
We’ve chosen C++ to demonstrate selection sort. You can use this as a reference to code in C, Java, Python, or any other programming language you prefer.
The sorted array is:
3 4 8 10 19
We’ve used the same input that we used in the example section above.
Initially, the current element was 19. We used a for loop to find the lowest number in the array — 3.
Using swap(), we swapped 19 with 3. The array changed to 3 10 4 8 19.
In the second run, the lowest number was 4, and we swapped it with the current element, which was 10. Changed array: 3 4 10 8 19.
The same steps were repeated until the array was sorted.
The time complexity of the selection sort algorithm is O(n^2).
Let’s look at the total number of comparisons made to get a better idea:
Total number of comparisons
= 1+ 2 + 3 + ……….+ (n - 3) + (n - 2)+ (n - 1)
Selection sort’s space complexity is O(1), as it doesn’t take any extra space.
Question 1: Is the selection sort algorithm an in-place, comparison-based sorting algorithm?
Answer: The selection sort algorithm is an in-place, comparison-based sorting algorithm. This basically means that this algorithm transforms a given input (in this case, an array) without using any other data structure. In such cases, the input is usually overwritten by the output.
Question 2: How many swaps does the selection sort algorithm make?
Answer: The selection sort algorithm makes n-1 swaps in the worst case and zero swaps in the best case. Therefore, it never makes more than O(n) swaps. So, it is handy in situations where “memory write” is a costly operation.
Question 3: Is the selection sort algorithm faster than bubble sort?
Answer: Both selection sort and bubble sort have a worst-case complexity of O(n^2). However, the selection sort algorithm is still faster than bubble sort in the worst-case scenario when “memory write” is a costly operation. This is because selection sort makes fewer swaps compared to bubble sort.
If you’re looking for guidance and help with getting started, sign up for our free webinar. As pioneers in the field of technical interview preparation, we have trained thousands of engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
Article contributed by Deepak Kumar
Attend our webinar on
"How to nail your next tech interview" and learn