Selection Sort in C

Introduction to Selection Sort in C

Selection Sort in C is a sorting algorithm that is used to sort a list of elements in either an ascending order or a descending order.

This algorithm chooses the minimum element from the list of elements and swaps it with the first element of the list. Similarly, it chooses the second minimum element from the list and swaps it with the second element of the list. It continue swapping the elements until all the elements of the list are completely sorted in either direction.

This selection sort in C is an in-place algorithm as it swaps the elements in the list itself. It does not require an extra list or array to sort the elements.

Algorithm of Selection Sort in C

The algorithm of the Selection Sort in C is as follows -

• Make a variable (say min_index) and initialize it to the location 0 of the array.
• Traverse the whole array to find the smallest element in the array.
• While traversing the array, if we find an element that is smaller than min_index then swap both these elements.
• After which, increase the min_index by 1 so that it points to the next element of the array.
• Repeat the above process until the whole array is sorted.

The whole algorithm has been depicted with the help of a pictorial representation below.

;

How to Implement Selection Sort in C?

We will be implementing the Selection sort in C by different techniques. However, the main approach would to select the smallest element from the array and replace it with the first element of the array. Similarly, we will be choosing the smallest element from the rest of the array skipping the first element because it is already in its correct position. We will keep doing this until our array becomes sorted.

Moreover, the other ways to implement the selection sort in c can be using a for loop, a while loop, and using functions as well.

How does Selection Sort Works in C?

selection sort in c works by dividing the array into two parts - one that will be sorted and the other that will be unsorted. After each step in the selection sort in c, we will be picking one element from the unsorted part and put it into the sorted part of the array.

It basically picks the smallest element from the unsorted part of the array and swaps it with the last index of the sorted part. This whole process of finding the smallest element in the array from the unsorted part and swapping it with an element of the sorted part repeats until the whole array is sorted in either ascending or descending order.

Example of Selection Sort in C

Let us take an example of how the selection sort in c actually works.

• Let's take an array arr that has the following elements.

  arr = {4,7,5,3,2,1}

• In the first pass of the array -

  • First of all, set the variable min_index=0 and then find the smallest element of the array which will be 1 in this case. Therefore, we will swap 1 with arr[min_index]

    Now, the array becomes arr = {1,7,5,3,2,4}

    

• In the second pass of the array -

  • We increment the min_index by 1 therefore min_index = 1. Now we will find the highest element for the rest of the array which comes out to be 2. Therefore, we will swap 2 with arr[min_index].

    Now, the array becomes arr = {1,2,5,3,7,4}

    

• In the third pass of the array -

  • The value of min_index = 2 and the highest element in the rest of the array comes out to be 3. Therefore we will swap 3 with arr[min_index]

    Now, the array becomes arr = {1,2,3,5,7,4}

    

• In the fourth pass of the array -

  • The value of min_index = 3 and the highest element in the rest of the array comes out to be 4. Therefore we will swap 4 with arr[min_index]

    Now, the array becomes arr = {1,2,3,4,7,5}

    

• In the fifth pass of the array -

  • The value of min_index = 4 and the highest element in the rest of the array comes out to be 5. Therefore we will swap 5 with arr[min_index]

    Now, the array becomes arr = {1,2,3,4,5,7}

    

Now, our array becomes sorted, therefore, we will stop the process.

Program to Perform Selection sort in C

In this approach, we will choose a min_index and assign it a value of the first location of the array. However, in the next iterations, its value keeps on increasing by 1.

The significance of this variable is to swap the smaller digits in the front of the array so that our array automatically gets sorted. However, we will then choose the smallest digit from the array and swap it with arr[min_index].

Let us see the code for the above approach to understand it better.

Output:

Therefore, as you can see in the above output, the array becomes sorted.

As you can see in the above code, first the min_index has been initialized with i such that it gets updated as soon as one iteration is completed. Further, the inner loop of j finds the smallest element from the rest of the elements. After which both these elements are swapped if the jth element is smaller than the min_index element.

Program to Perform Selection sort in C Using For Loop

Now, let us see a simple program to perform selection sort using the for loop in C. In this approach, we will use two nested for loops, the first loop i will be running from 0 to less than n whereas the second loop j will be running from i+1 to less than n.

Inside the loop, if the jth element is smaller than the ith element then we swap the ith and jth element with each other and similarly check for other elements as well.

Let us see how to implement this approach using for loops.

Output:

Therefore, as you can see in the output, the elements of the array are now sorted.

However, in the above code, we swap the ith and jth element as soon as we get a smaller ith element in the array. After which we simply print our sorted array.

Program to Perform Selection sort in C Using While Loop

This is another approach in which we use the while loop to sort the array elements using selection sort.

This approach is very similar to the previous for loop approach as the logic remains the same only the for loop has been converted to a while loop.

Let us see the code for the same.

Output:

In the above approach, we have used the while loop to perform the selection sort in C. There are two loops i and j and the ith and jth element are swapped if the jth element is smaller than the ith element in the array.

Program to Perform Selection sort in C Using Functions

In this approach, we have used placed our logic into a function so that it can be called in the main program whenever needed and we need not to write the same code for sorting again and again.

Let us see the code for the same.

Output:

In this approach, we have divided our logic of selection into different functions. The Selection sort in C logic goes in the function selectionSort whereas the swapping logic goes in the swap function.

However, the logic remains the same if we find a smaller element then we swap it.

Complexity of Selection sort in C

The time complexity of the selection sort program in C will be $O(n^2)$ in all three cases - worst, best, and average.

However, the worst case happens when the array is sorted in descending order and we have to sort it in ascending order.

The best case happens when the array is already sorted.

The average case happens when the array is neither sorted in ascending order nor descending order, it is rather in a jumbled fashion.

The complexities in all three cases will be in the order of $N^2$.

However, the space complexity for all three cases will be O(1) as the program for the selection sort does not take any extra space to sort the elements in a particular order.