Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Selection Sort Algorithm

Last updated by Dipen Dadhaniya on Sep 25, 2024 at 11:01 PM | Reading time: 7 minutes

The fast well prepared banner

Attend our Free Webinar on How to Nail Your Next Technical Interview

WEBINAR +LIVE Q&A

How To Nail Your Next Tech Interview

Selection Sort Algorithm
Hosted By
Ryan Valles
Founder, Interview Kickstart
strategy
Our tried & tested strategy for cracking interviews
prepare list
How FAANG hiring process works
hiring process
The 4 areas you must prepare for
hiring managers
How you can accelerate your learnings

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:

  • What Is Selection Sort?
  • How It Works — With Example
  • Selection Sort Algorithm
  • Selection Sort Pseudocode
  • Selection Sort Code
  • Selection Sort Complexity
  • Advantages of Selection Sort
  • Disadvantages of Selection Sort
  • Selection Sort FAQs

What Is Selection Sort?

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.

Selection Sort Working Principle

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).

Selection Sort Example

Consider the following example:

Input array: 

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!

Selection Sort Algorithm

Now that you know how selection sort works, following the algorithm steps will be pretty easy:

  • Step 1: Set minIndex to position 0
    (minIndex will hold the index of the smallest number in the unsorted subarray)
  • Step 2: Search for the smallest element in the unsorted subarray and update minIndex
  • Step 3: Swap the element at the position minIndex with the first element of the unsorted subarray.
  • Step 4: Again set minIndex to the first position of the  unsorted subarray
  • Step 5:  Repeat steps 2 to 4 until the array gets sorted

Selection Sort Pseudocode 

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.


procedure selection sort
arr : array of integers
n : size of the array

for i =1 to n-1
// set current element as minIndex
minIndex=i
// check for all other element(right side of current element) 
for j =i+1 to n
		if(arr[j] < arr[minIndex])
			minIndex=j
		end if
end for

// swap  the current element with the minimum element to the right side
swap(arr[minIndex], arr[i])
end for
End procedure


Selection Sort Code in C++

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.



#include
using namespace std;

void selectionSort(int arr[], int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		// finding minimum element of unsorted subarray
		int minIndex = i;
		for (int j = i + 1; j < n; j++)
		{
			// updating the minimum element
			if (arr[j] < arr[minIndex])
			{
				minIndex = j;
			}
		}
		swap(arr[i], arr[minIndex]);
	}

	cout << "The sorted array is: " << endl;
	for (int i = 0; i < n; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

int main()
{
	int arr[] = {19, 10, 4, 8, 3};
	int n = sizeof(arr) / sizeof(arr[0]);
	selectionSort(arr, n);
	return 0;
}

Output:

The sorted array is: 

3 4 8 10 19 

Code Explanation 

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.

Selection Sort Complexity

Time Complexity

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) 

= n*(n-1)/2

= O(n^2)

  • Worst-case complexity: O(n^2)
    When the input array is sorted in descending order
    In this case, n-1 swaps are performed
  • Best-case complexity: O(n^2)
    When the array is already sorted (ascending order)
    In this case, no swap operation is performed
  • Average-case complexity: O(n^2)
    When the array is neither sorted in ascending nor in descending order

Space Complexity

Selection sort’s space complexity is O(1), as it doesn’t take any extra space. 

Advantages of Selection Sort

  • Is easy to implement
  • Works well on small lists
  • Does not require additional temporary storage

Disadvantages of Selection Sort

  • Does not work well for huge lists of items; has a poor run time — n^2 for n elements
  • Is not adaptive: For example, an optimized bubble sort algorithm will take O(n) time to run on a sorted array, as it is adaptive. But selection sort will take O(n^2) in every case

Selection Sort FAQs

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.

Are You Ready to Nail Your Next Coding Interview?

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!

Sign up now!

----------

Article contributed by Deepak Kumar

Last updated on: 
September 25, 2024
Author

Dipen Dadhaniya

Engineering Manager at Interview Kickstart

Attend our Free Webinar on How to Nail Your Next Technical Interview

Register for our webinar

How to Nail your next Technical Interview

1
Enter details
2
Select webinar slot
First Name Required*
Last Name Required*
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

Selection Sort Algorithm

Worried About Failing Tech Interviews?

Attend our webinar on
"How to nail your next tech interview" and learn

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Our tried & tested strategy for cracking interviews
blue tick
How FAANG hiring process works
blue tick
The 4 areas you must prepare for
blue tick
How you can accelerate your learnings
Register for Webinar
entroll-image