











Selection Sort in C
What is Selection Sort in C
In this Sorting technique the list is divided into two parts. first one is left end and second one is right end . The selection Sort is very simple sorting algorithm.


Time Complexity (Best) | Ω(n2) |
Time Complexity (Avg) | Θ(n2) |
Time Complexity (Worst) | O(n2) |
Space Complexity | O(1) |
Steps for Selection Sort in C
There are following Step of selection sort algorithm.
- Step 1-Select the smallest value in the list.
- Step 2-Swap smallest value with the first element of the list.
- Step 3-Again select the smallest value in the list (exclude first value).
- Step 4- Repeat above step for (n-1) elements untill the list is sorted.


Implementation of Selection Sort
- We have been given a unsorted array. which we’ll make a sorted array using selection sort. first of all find the smallest value in the array and then swap smallest value with the starting value.
- According to the below image, 8 is smallest value in this array so 8 is swapped with the first element that is 72.
- Similarly, in the next iteration we’ll find the next smallest value, excluding the starting value so in this array 10 is second smallest value, which is to be swapped with 50.
- These iteration will continue until we have the largest element to the right most end, along with all the other elements in their correct position.
- And then we can finally say that the given array is converted in sorted array.


Code of Selection sort in C
// C program for implementation of selection sort // Time Complexity : O(N^2) // Space Complexity : O(1) // Best, Avg, Worst Cases : All of them O(N^2) #include<stdio.h> /* Display function to print values */ void display(int array[], int size) { int i; for (i=0; i < size; i++) printf("%d ",array[i]); printf("\n"); } // The main function to drive other functions int main() { int array[] = {72, 50, 10, 44, 8, 20}; int size = sizeof(array)/sizeof(array[0]); printf("Before sorting: \n"); display(array, size); int i, j, min_idx,temp; // Loop to iterate on array for (i = 0; i < size-1; i++) { // Here we try to find the min element in array min_idx = i; for (j = i+1; j < size; j++){ if (array[j] < array[min_idx]) min_idx = j; } // Here we interchange the min element with first one temp = array[min_idx]; array[min_idx] = array[i]; array[i] = temp; } printf("\nAfter sorting: \n"); display(array, size); return 0; }
// C program for implementation of selection sort // Time Complexity : O(N^2) // Space Complexity : O(1) // Best, Avg, Worst Cases : All of them O(N^2) // C program for implementation of selection sort #include<stdio.h> // function to swap item using pointers void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; } void selectionSort(int array[], int size) { int i, j, min_idx; // Loop to iterate on array for (i = 0; i < size-1; i++) { // Here we try to find the min element in array min_idx = i; for (j = i+1; j < size; j++) { if (array[j] < array[min_idx]) min_idx = j; } // Here we interchange the min element with first one swap(&array[min_idx], &array[i]); } } /* Display function to print values */ void display(int array[], int size) { int i; for (i=0; i < size; i++) printf("%d ",array[i]); printf("\n"); } // The main function to drive other functions int main() { int array[] = {72, 50, 10, 44, 8, 20}; int size = sizeof(array)/sizeof(array[0]); printf("Before sorting: \n"); display(array, size); selectionSort(array, size); printf("\nAfter sorting: \n"); display(array, size); return 0; }
Output
Before sorting:
72 50 10 44 8 20
After sorting:
8 10 20 44 50 72
Performance
The Selection Sort best and worst case scenarios both follow the time complexity format O(n^2) as the sorting operation involves two nested loops. The size of the array again affects the performance.[1]
Strengths
- The arrangement of elements does not affect its performance.
- Uses fewer operations, so where data movement is costly it is more economical
Weaknesses
- The comparisons within unsorted arrays requires O(n^2) which is ideal where n is small




Time Complexity
For Selection Sort
Best
Ω(n2)
Average
Θ(n2)
Worst
O(n2)
Space Complexity
O(1)





Question 1. Array = [10, 11, 12, 13, 14, 15], the number of iterations bubble sort(without flag variable) and Selection sort would take –
- 5 and 5
- 5 and 4
- 4 and 4
- 6 and 6
(Cognizant – Mettl Test)
In bubble sort they are talking about passes, even though the question says iterations.
A bubble sort with n items takes (n-1) passes.
In selection sort also for n items its (n-1) passes.
Thus, 4 and 4 is answer
Option C





Question 2. Array = [10, 11, 12, 13, 14, 15], the number of iterations bubble sort(with flag variable) and Selection sort would take –
- 5 and 5
- 5 and 4
- 4 and 4
- 1 and 4
(Cognizant – Mettl Test)
In bubble sort they are talking about passes, even though the question says iterations.
A bubble sort with n items takes (n-1) passes. But, since the whole array is sorted, bubble sort will have just one pass to realize the array is sorted and abandon other passes
In selection sort also for n items its (n-1) passes, even though the array is sorted
Thus, 1 and 4 is answer
Option C





Question 3. What is the best case complexity of selection sort?
- O(nlogn)
- O(logn)
- O(n)
- O(n2)
(Wipro – AMCAT Test)
In selection sort all cases the time complexity is : O(N^2)
Explanation: The best, average and worst case complexities of selection sort is O(n2).
(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2.





Question 4. Array[] = {72, 50, 10, 44, 8, 20} how would the array look like in iteration 4
- 8, 10, 44, 20, 72, 50
- 8, 10, 20, 44, 72, 50
- 8, 10, 20, 44, 50, 72
- None
(Wipro – AMCAT Test)
Answer : B
The array will look like – 8, 10, 20, 44, 72, 50
Check image
Sorting
Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.


Login/Signup to comment