Write a selection sort program in C. Given an unsorted array, write a c code to sort an array using selection sort.
For example :
Input : {9, 8, 19, 2, 3 }
Output : { 2, 3, 8, 9, 19}
After sorting, array elements are arranged in a sorted order.
Selection Sort
Selection sort is an in-place comparison technique. In selection sort, we pick minimum element and move an element to it’s correct position. We repeat this process until all the elements are sorted.
Let’s understand this process in detail. In Selection sort, we divide an array into two parts sorted (left end) and unsorted (right end). Initially the sorted part is empty and we consider complete array as an unsorted.
We perform following steps to sort an array –
i) At each iteration, we pick the minimum element from the unsorted subarray.
ii) Then Swap it with the leftmost element of the unsorted subarray.
iii) As we put the element to it’s correct position, the size of the sorted array is keep increasing and unsorted is decreasing. At the end we get the sorted array.
Selection Sort Explanation with Example – Step by Step
The time complexity of selection sort is O(n^2). It is not suitable for large data sets.
How Selection Sort Works?
Selection sort is an in-place comparison sort, in which both searching and sorting take place. In each iteration, we pick the smallest or largest element and move to its proper place .
I have added video tutorial at the end of this post for better understanding.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
7 5 1 3 6 // Input element /* In first step 1 is exchanged with 7 . */ Step 1 : 1 5 7 3 6 /* In second step 5 is exchanged with 3. */ Step 2 : 1 3 7 5 6 /* In third step 5 is exchanged with 7 */ Step 3 : 1 3 5 7 6 /* In fourth step 6 is exchanged with 7 */ Step 4: 1 3 5 6 7 |
In the above example, We have 5 elements in an array so it requires 4 steps to sort an array. Here is the Pseudo code for selection sort algorithm.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
for (i = 0; i < n-1; i++) { /* Assume min. element is i. */ index = i; /* Start second loop. */ for ( j = i+1; j < n; j++) { /* if this element is less, then it is the new minimum */ if (a[j] < a[index]) { /* Replace the value of minimum */ index = j; } } /* Swap the position. */ swap(a[i], a[index]); } |
Selection Sort Program in C
Selection Sort Program in C
We have discussed the logic. Let’s write a code of selection sort in C.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/ * C Program to Implement Selection Sort Algorithm */ #include <stdio.h> int main() { int n,i,j,temp,arr[100],index; printf("How many elements you want to enter "); scanf("%d",&n); printf("Enter elements\n"); /* Taking input from user. */ for(i=0; i<n; i++) scanf("%d",&arr[i]); for(i=0; i<n; i++) { /* Assign the value of i. */ index = i; for(j=i+1; j<n; j++) { if(arr[j]<arr[index]) { index = j; } } /* Swap the element */ temp = arr[index]; arr[index] = arr[i]; arr[i] = temp; } printf("After sorting is: "); for(i=0; i<n; i++) { printf(" %d",arr[i]); return 0; } |
In this video tutorial, I have explained how selection sort works and their implementation using java and c code.
