Introduction to Selection Sort

Sorting algorithm 01

Gunavaran Brihadiswaran
Mar 2 · 3 min read
Image by author

Selection sort is one of the basic sorting algorithms which is easy to understand and implement. The idea is simple: given an array of elements to be sorted,

Let’s look at an example for better understanding.

Suppose the array of numbers to be sorted in ascending order is (8,4,6,3,1,9,5)

Image by author

Initially, the entire array will be the unsorted subarray as shown in the figure above. We find the minimum value 1 and swap it with 8, which is the first element of the unsorted subarray. The sorted subarray is colored in yellow. The next minimum value in the unsorted subarray is 3. We swap it with 4 which is the first element of the unsorted subarray. Thus, in the iᵗʰ iteration, we swap the minimum value with the iᵗʰ element of the array. After m number of iterations, the first m elements of the array will be in sorted order.

Implementation in C

Analysis of Selection Sort

Image by author

Hence, the total number of comparisons required would be (n-1) + (n-2) + ….. + 2 + 1 which can be simplified as n(n-1)/2 → O(n²)

Since its time complexity is quadratic, selection sort would be very inefficient when a large number of elements has to be sorted. However, since its space complexity is O(1), selection sort can be useful when the amount of memory available is very limited.

Hope you enjoyed the article!

Nerd For Tech

From Confusion to Clarification

Gunavaran Brihadiswaran

Written by

A Computer Science Research Student who loves to do Research, Write and Travel

Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/. Don’t forget to check out Ask-NFT, a mentorship ecosystem we’ve started

Gunavaran Brihadiswaran

Written by

A Computer Science Research Student who loves to do Research, Write and Travel

Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/. Don’t forget to check out Ask-NFT, a mentorship ecosystem we’ve started

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store