Searching and sorting have always been pain points in computing, needing consistent improvements to tackle concerns. Regardless, its importance in computational processes is imperative to deal with data sorting and arrangement.
In simple terms, sorting algorithms work to sort a sequence of elements. These elements could be numbers, characters, or anything – but the purpose is to sort the list in order quickly. Take the following example: We have the input as an array of numbers – [2, 6, 4, 3, 9, 1]. A sorting algorithm can transform this input array into this sorted array – [1, 2, 3, 4, 6, 9]. The sorting algorithm should also work with characters and sort them based on ASCII values.
Check out our free courses to get an edge over the competition.
As easy as the task seems for humans, computers use several sorting algorithms designed over the decades to accomplish this task. Some of the most famous sorting algorithms include:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Counting Sort
- Radix Sort
- Bucket Sort
- Heap Sort
- Shell Sort
These algorithms differ in execution, which results in a huge difference in time and space complexities. Each of these algorithms has different use cases, and it is something that you must explore. Though, this article specifically explores one sorting algorithm- the Selection Sort.
Learn Software Development Courses online from the World’s top Universities. Earn Executive PG Programs, Advanced Certificate Programs or Masters Programs to fast-track your career.
Let’s begin our understanding of Selection Sorting in C by understanding its algorithm before diving into its code implementation using the C programming language.
Selection sort algorithm – for sorting in ascending order
Follow these steps to implement selection sorting in C on a sequence of numbers, to arrange them in ascending order.
- Start by finding the minimum element in the array. Swap that element with the element present in the first position.
- Now, in the remaining array, from the second element onwards, find the minimum element again, and swap it with the element in the second position. This gives us the first two elements in the correct position.
- Repeat this process n-1 times till the array ends to get the final sorted array in ascending order.
Explore our Popular Software Engineering Courses
If you have ever played a game of cards, these are precisely the steps you follow to sort your cards in place. Find the smallest card, put it in the first position, then from the remaining cards, find the smallest card again, put it in the second position, and so on. Naturally, this comes instinctively to us and is easier to do, but this is a precise sorting algorithm at its core!
Let’s look at how we can implement Selection Sort in C++ or C using a sample program.
Check out upGrad’s Advanced Certification in DevOps
Implementation of Selection Sort in C++ or C
int array, n, c, d, position, t;
printf(“Enter the number of elements\n”);
printf(“Enter %d integers\n”, n);
for (c = 0; c < n; c++)
for (c = 0; c < (n – 1); c++) // finding minimum element (n-1) times
position = c;
for (d = c + 1; d < n; d++)
if (array[position] > array[d])
position = d;
if (position != c)
t = array[c];
array[c] = array[position];
array[position] = t;
printf(“Sorted list in ascending order:\n”);
for (c = 0; c < n; c++)
Check out upGrad’s Advanced Certification in Blockchain Technology
If you compile and run this C program, you will receive the following output:
>Enter the number of elements
>Enter 5 integers
5, 3, 2, 7, 1
>Sorted list in ascending order:
1, 2, 3, 5, 7
The above program returns you the sorted list of input numbers in ascending form, and the algorithm used to achieve this output is the Selection Sort algorithm.
In-Demand Software Development Skills
While it should be intuitive how Selection Sort works, let’s take an example and try to dry run the Selection Sort algorithm and code to dissect how it works in real-time.
Understanding the working of Selection Sort
To understand how Selection Sort works, let’s take an unsorted array of integers and follow along with the algorithms. Here are our numbers:
12, 29, 25, 8, 32, 17, 40.
Scan the entire list sequentially and find the minimum element from the entire array. Here, 8 is found to be the minimum element. So, 8 will be sent to the 0th index (first position), and the element at the 0th index will be sent to the previous index of 8 (note that the items in bold are those that have been swapped):
8, 29, 25, 12, 32, 17, 40.
For the second position, where we currently have 29, we will again scan the list from the second element to the last element and find the smallest element there. We find that 12 is the smallest element now. So, we swap 12, and the element currently presents in the second position, i.e., 29. Here is what you get:
8, 12, 25, 29, 32, 17, 40.
Read our Popular Articles related to Software Development
We now have the first two elements of our array in their right place – sorted properly.
This process is repeated for all the indexes until a sorted array is achieved. The entire working process looks like this:
What we finally receive at the end is a completely sorted array in ascending order. But how efficient is this algorithm? How does it stand with other sorting algorithms?
The efficiency of algorithms is measured using space and time complexity. Let’s understand the efficiency of our Selection Sort algorithm on both of these fronts.
Running complexity of Selection Sort
Let’s look at both the time and space complexity of Selection Sort. We’ll check out the complexity in all three cases – best, worst, and average, in order to get a complete picture.
1. Time complexity
- Best Case Complexity occurs when the input array is already sorted, so the algorithm doesn’t need to perform any sorting. Even in that case, our Selection Sort algorithm will need to check all the elements again to ensure they’re in their right places to bring best-case complexity to O(n2).
- Average Case Complexity is when the input array elements are presented in a jumbled order, a mix of ascending and descending orders. In that case, too, the time complexity is O(n2).
- Worst Case Complexity is when the input array is in descending order and needs to be reversed entirely to bring it to the required sorted order. In this case, too, the complexity O(n2).
The complexity of our Selection Sort algorithm is O(n2) in all three cases. The reason for this is the algorithm runs through all the elements to check their correct position, regardless of the state of the input array. O(n2) is not a good time complexity for an algorithm, making Selection Sort slower, especially when compared to other sorting algorithms like Heap Sort and Merge Sort.
2. Space Complexity
The space complexity of the Selection Sort is O(1), which means our algorithm does not require additional memory space to perform computation. All of the comparisons and swapping happen in the original input array itself. This also makes this approach a stable sort.
The world of sorting and searching is truly fascinating and full of new things to learn and explore. Selection Sort is just the beginning of it. If you understood Selection Sort and have implemented it successfully, your goal should be to dive deeper into different sorting techniques and try to analyze them yourself. That is how you will become a better programmer and, eventually, a better software developer.
Software development, after all, is all about knowing the right set of tools, having the correct knowledge, and persevering with it. At upGrad, we understand the essence of software development and impart the same to our learners. Our courses are designed for students from varied backgrounds and often demand no strict prerequisite. One such course is the Full Stack Development Certificate Program.
This fully online course, lasting nine months, requires no coding experience and helps you build your career in full-stack development. The course starts on 30th June, so get yourself registered soon!
Is Selection Sort a favorable sorting method?
Selection Sort does not fare well in time complexity, so it isn’t a highly recommended sorting approach.
What is the time complexity of Selection Sort?
Selection Sort operates with the time complexity of O(n^2) in all three - best, worst, average - cases.
Is Selection Sort stable?
Yes, the Selection Sort is stable.