C program for selection sort: Selection sort is one of the sorting techniques used for arranging the unordered data into an ordered form, which is in increasing order. C program for selection sorting will sort the data by repeatedly selecting the smallest (largest) element from the unsorted region and swapping it with the first element of the unsorted region.
Let us learn the code for the C program for selection sort. You can start your career with PW Skills Complete Decode Full Stack Web Dev 1.0 to boost your career and give you a strong foundation. The complete course offers recorded and live lectures and any-time doubt-solving.
What is Selection Sort?
Selection sort is a simple sorting technique that selects the smallest element by traversing the complete array or list and swapping it with the unsorted part. There will be a total of N-1 passes during sorting. It is a linear sorting algorithm with an O(N^2) quadratic time complexity.
Also Check: What is Quick Sort and how does it work?
C Program for Selection Sort Approach
The approach for the following C program for selection sort is given below.
- Start
- Initialise a variable named min_ind, which will store 0 at the beginning.
- Now, run a loop to find the minimum element in the array.
- If you find any smaller elements than min_ind, then swap both values.
- Now, increment min_ind++ to point to the next element in the array.
- Keep repeating until you reach the size of the array or list.
- End
C Program For Selection Sort Algorithm
The Algorithm for selection sort is given here in the table.
|
C Program For Selection Sort Algorithm |
| selectionSort (array, size)
loop i from 0 to size – 2 set min_ind as i loop j from first unsorted to size – 1 check if array[j] < array[min_ind] set min_ind as j swap array[i] with array[min_ind] end for end selectionSort |
C Program For Selection Sort
Selection sort is used for arranging the unsorted data in a list in increasing or decreasing order. Let us learn the C program for selection sort in the table below.
|
C Program for Selection Sort |
| #include <stdio.h>
void selection_sort(int arr[], int n) { int i, j, min_index; // Traverse through all array elements for (i = 0; i < n – 1; i++) { // Find the minimum element in the unsorted part of the array min_index = i; for (j = i + 1; j < n; j++) { if (arr[j] < arr[min_index]) { min_index = j; } } // Swap the found minimum element with the first element int temp = arr[i]; arr[i] = arr[min_index]; arr[min_index] = temp; } } int main() { int my_array[] = {64, 25, 12, 22, 11}; int n = sizeof(my_array) / sizeof(my_array[0]); // Perform selection sort selection_sort(my_array, n); // Print the sorted array printf(“Sorted array: “); for (int i = 0; i < n; i++) { printf(“%d “, my_array[i]); } printf(“\n”); return 0; } |
Working of C Program For Selection Sort
Let us understand the working of selection sort with the help of an example.
Consider an array “arr” containing 5 elements. arr[]= {34, 23,11,65,9}. Now, we will use Selection Sort to arrange these data items in ascending order.
First Pass:
- Initialize the min_ind with 0.
- For the first pass, the complete array is traversed from 0 to N-1 i,e. 4 to find the lowest value which is clearly 9. Then we swap this minimum element with our min_ind element which is at 0.
Second Pass:
- Now we increment the min_ind to point at the first index. Min_ind = 1.
- Now let us find the minimum element, which is 11. Now we swap 11 with the min_ind.
Third Pass
- Now, increment min_ind by 1. The min_ind will now point to the 2 element which is min_ind=2.
- Now, traverse the array and find the lowest element. No element is smaller than the element at min_ind.
Fourth Pass
- In the fourth pass the min_ind is incremented to 3rd index. Now swapping is done as no element was smaller than the min_ind.
- Now min_ind = 3
- Traverse the array and find the lowest element which is 34. Swap this minimum value with the min_ind.
Fifth Pass
- In the fifth pass, all the elements are now sorted in increasing order automatically.
Advantages of C Program for Selection Sort
Selection Sort is one of the simplest and most efficient sorting algorithms. It starts sorting the element by repeatedly selecting the smallest element by traversing the complete array. Let us know some of the advantages of the C program for selection sort.
- The selection sort is a very simple sorting algorithm and hence, it is easy to understand.
- The selection sort is an in-place sorting algorithm. No extra space is required for sorting in this algorithm.
- Selection sort works better for small datasets or arrays. The time complexity of the selection sort is O(N^2).
- In selection sort, we only perform one swap for each pass hence, the number of swaps is reduced. This will reduce the cost of swapping.
Also Read: What are Array in C
Disadvantages of C Program For Selection Sort
Selection Sort is one of the sorting algorithms we learn in data structures. However, there are some shortcomings in the selection sort. Let us know some disadvantages here.
- The selection sort has quadratic time complexity in order of O(N^2) where N is the number of elements. This shows that the time required for sorting grows quadratically with the size of the input.
- Selection sort is not an adaptive sorting algorithm.
- It is not a stable algorithm. Hence, it fails to preserve the relative order of data items with equal values.
- It is not suitable for large datasets or arrays.
Also Check: What is Recursion in C
Complexity Analysis of C Program For Selection Sort
Given here are the time complexity and space complexity table for the selection sort.
|
C Program For Selection Sort Complexity Analysis |
|
| Complexity Type | Selection Sort |
| Time Complexity | O(n^2) |
| Space Complexity | O(1) |
| Recommended Reads | |
| Java Vs C++ Vs Python | Java or C++ which is better |
| What is STL in C++ | Top Features of C++ programming language |
C Program For Selection Sort FAQs
Q1. What is selection sort?
Ans: Selection sort is a simple sorting technique that selects the smallest element by traversing the complete array or list and swapping it with the unsorted part.
Q2. What is the time complexity of the Selection sort?
Ans: The time complexity of the selection sort is O(N^2).
Q3. Is Selection Sort Stable?
Ans: No, the selection sort is unstable as it does not preserve the relative order of data items with equal values.
Q4. Is Selection Sort a divide-and-conquer sorting algorithm?
Ans: No, Selection sort does not follow a divide a conquer approach to sort the data items. It repeatedly selects the smallest elements by traversing the complete array and swaps the value until the list is sorted.
