How to Implement Selection Sort in C?

In this article, we are going to learn how to implement one of the sorting algorithms, Selection Sort in C Language. We will be looking at the intuition and approach before coding up the selection sort program in C. Let us first understand how the selection sort works.

Breaking Down Selection Sort

Selection Sort is a comparison-based and in-place sorting algorithm which takes an element and compares it to all other elements before placing it at its correct position in the set of elements.

Before hopping on to the implementation of selection sort in c, let’s take a real-world example, we can assume students standing in a school assembly in an unordered manner and they must stand from shortest to tallest to make everyone see the podium without any difficulties. We will pick the first one and compare it with anyone who is shorter than the student at the front, we will keep replacing it till we keep getting a student with a shorter height.

Once we are done finding the student who is going to stand in the first place, we move to check for the student who is going to be placed in the second position with the second shortest height.

Till we end up with the student with the second last position, we will not be done with the selection. Similar to this, we apply logic and conditions to execute the selection sort algorithm in c.

Algorithm for Selection Sort in C

The Selection Sort program in C to sort the array in ascending order can be implemented in a few easy steps as mentioned:

  1. Declare an array of size, n.
  2. Provide the n inputs such that the array is unsorted.
  3. Loop i, from 0 to n-2
  4. Inner loop j runs from i+1 to n-1
  5. On each iteration of j:
    • If arr[i] > arr[i] then we swap the number in order to sort the array in ascending order.
    • Else continue
  6. Print the sorted array

In this manner, the array will be sorted in ascending order will the lowest element at the start and the largest at the end position. Looking at the algorithm, its gives an idea to do the selection sort program in c.

Dry Run for Selection Sort

To understand selection sort in c with more clarity, let us look at the dry run of the program.

We have an array sorted in descending order as 20,10,8,5,1. Our task is to sort this array in ascending order using the selection sort algorithm in c. The approach to solving is as follows explained using various passes.

First Pass: We will compare 20 with 10 and the position will be swapped, we will still be at index i, where 10 is lying and now we will compare 10 (at index 0) with the element at index 2 i.e. 8 and swapping will be performed. Similarly, 5 and 1 will switch the position with index 3 and index 4

Second Pass: The first index is having the smallest element and we will start to find the number for 1st index or second smallest with 20 switching places with 10, 10 with 8 and lastly 8 with 5.

Third Pass: First two elements are already sorted and we will start checking from index 2, 20 will switch its places with 10 and 10 will be swapped with 8.

Fourth Pass: We will be standing at the second last position and also the last comparison that needs to be made between the last element and the second last, where 20 will be replaced with 10 and further winding up the selection sort program in C.

The sorted array obtained is going to be 1,5,8,10 and 20.

Code for Selection Sort in C

#include<stdio.h>
int main(){
	int a[10],i;
	int j,temp,num;
	
	printf("Enter the number to give\n");
	scanf("%d",&num);
	
	for(i=0; i<num; i++){
		printf("a[%d]=\t",i);
		scanf("%d",&a[i]);
	}
	
	for(i=0; i<num-1; i++){  
		for(j=i+1;j<num; j++){
			if(a[i]>a[j]){
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
		}
	}

printf("Selection Sort in C\n");
for(i=0; i<num; i++){
		printf("a[%d]=\t%d\n",i,a[i]);
	}
	
	return 0;
}
Input:
5
20
10
8
5
1

Output:
1
5
8
10
20

Complexity of Selection Sort
Selection sort algorithm in c ( or in general any language ) has a space complexity of O(1) as there is no extra space used being a comparison-based and in-place sorting algorithm.

Talking about time complexity, it is going to be O(n*n) as there are two loops and each iteration in the outer loop is going to make n comparisons. Assuming there are five elements in the array then 25 comparisons are made to sort the array using Selection Sort algorithm in C.

Conclusion

In this article, we started with the practical working of selection sort and later got to know the mechanism of the selection sort algorithm in c along with its dry run.

We studied how to solve the selection sort program in c and analyzed the space and time complexity of this sorting algorithm. We hope that you have understood everything in detail from this article on Selection Sort Program in C. Find more articles like this on Prep Bytes.

FAQs Related to Selection Sort Algorithm in C

1. What is in-place sorting?
In-place means that all the operations which be made without using any additional data structure for their execution. Selection Sort in C or any specific language uses in-place sorting.

2. What is the time complexity of the Selection Sort Program in C?
Selection Sort Program in C takes O(n^2) as two loops are going to run N-1 time where one decides the value at index and inner loops check for all the succeeding indexes element.

Even the best-case time complexity of the selection sort algorithm in C ( or other languages in general ) is going to be O(n^2).

Other C Programs

C Program for Binary Search
C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C
Selection Sort Program in C

Leave a Reply

Your email address will not be published. Required fields are marked *