How to Implement Selection Sort in C?

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
• Quicksort
• 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

A straightforward and intuitive sorting algorithm called selection sort divides the input list into two sections: the sorted and the unsorted. It repeatedly chooses the smallest or largest element from the unsorted portion and swaps it with the element in the proper position in the sorted portion. The list is sorted until the end.

One of the key advantages of the selection sort program in C is its simplicity. The algorithm is easy to understand and implement, making it a popular choice for educational purposes and small datasets. Additionally, selection sort is an in-place sorting algorithm that operates directly on the input array without requiring extra memory space for auxiliary data structures. This characteristic can be advantageous in situations where memory is limited.

In all cases, the algorithm’s time complexity is given as O(n^2). This quadratic time complexity makes selection sort inefficient for large datasets, as the number of comparisons and swaps increases exponentially with the input size. Consequently, selection sort is generally not recommended for large-scale sorting tasks when more efficient algorithms, such as merge sort or quicksort, are available.

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. 

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! 

A selection sort example in C also exhibits poor performance characteristics when the input array is already partially sorted or contains repeated elements. Regardless of the initial order, a selection sort example in C always performs the same number of comparisons and swaps. This lack of adaptability contributes to its inefficiency compared to other sorting algorithms, which can exploit existing orders or other patterns to improve performance.

Despite its limitations, selection sort does have practical use cases. It can be beneficial when sorting small datasets or when simplicity and ease of implementation are prioritized over efficiency. Selection sort’s deterministic nature makes it a stable sorting algorithm, meaning it preserves the relative order of elements with equal values. This stability can be advantageous in certain scenarios where maintaining the original order is important.

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

#include <stdio.h>
int main()
{
  int array[100], n, c, d, position, t;
  printf("Enter the number of elements\n");
  scanf("%d", &n);
  printf("Enter %d integers\n", n);
  for (c = 0; c < n; c++)
    scanf("%d", &array[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++)
    printf("%d\n", array[c]);
  return 0;
}

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

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. 

Algorithmic Steps of Selection Sort:

1. Start with the first element as the current minimum.
2. Compare the current minimum with the next element in the unsorted part of the array.
3. If a smaller element is found, update the current minimum.
4. Continue comparing the current minimum with the remaining unsorted elements.
5. Swap the current minimum with the first element of the unsorted portion.
6. Keep repeating the steps 1-5 until the whole array is sorted.

Consider this:

```c
#include <stdio.h>
void selectionSort(int arr[], int n) {
  int i, j, minIndex, temp;
  for (i = 0; i < n - 1; i++) {
    minIndex = i;
    for (j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // Interchange the minimum element with the first element of the unsorted portion
    if (minIndex != i) {
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
}
int main() {
  int arr[] = {64, 25, 12, 22, 11};
  int n = sizeof(arr) / sizeof(arr[0]);
  selectionSort(arr, n);
  printf("Sorted array: \n");
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  return 0;
}
```

In this implementation, the `selectionSort` function takes an array `arr` and its size `n` as input. It iterates through the array and finds the minimum element in the unsorted portion for each iteration. If a smaller element is found, it updates the `minIndex`. After each iteration, it swaps the minimum element with the first element of the unsorted portion.

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. 

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.

In Conclusion

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!