This blog post explains Selection Sort Algorithm and its implementation using the C programming language. So before writing the C code for the Selection Sort Algorithm let’s first understand the Selection Sort Algorithm.
What is Selection Sort Algorithm:
Selection sort is an in-place comparison sorting algorithm. It has an O(n2)
time complexity, which makes it inefficient on large lists.
The selection sort algorithm sorts an array by selecting the smallest element from an unsorted list in each iteration and putting it at the beginning of the unsorted list.
The algorithm divides the input array (list) into two parts:
1. A sorted subarray of items. Initially, the sorted subarray is empty.
2. Remaining unsorted items that occupy the rest of the array. Initially, the unsorted subarray is the entire input array.
Selection Sort Algorithm Steps:
Let’s see the required steps to sort a list using the Selection Sort algorithm. Suppose unsorted list is (11
, 25
, 10
, 22
, 64
).
1. Set the first element as a minimum:
Sorted Sublist | Unsorted Sublist | Least element in Unsorted list |
() | (11 , 25, 10, 22, 64) |
11 |
2. Compare minimum element with other elements:
After selecting the first elements as a minimum. Compare the minimum with the second element. If the second element is smaller than the minimum, assign the second element as minimum otherwise do nothing.
After that compare the minimum with the third element. Again, if the third element is smaller, then assign minimum to the third element otherwise do nothing. Repeat the same process until the last element.
Sorted Sublist | Unsorted Sublist | Least element in Unsorted list |
() | (11 , 25, 10, 22, 64) |
11 |
() | (11 , 25 , 10, 22, 64) |
11 |
() | (11 , 25, 10 , 22, 64) |
10 |
() | (11, 25, 10 , 22 , 64) |
10 |
() | (11, 25, 10 , 22, 64 ) |
10 |
3. Swapping minimum with left most unsorted array element:
After each iteration, the minimum is placed in the front of the unsorted list. You can see the table now 10
swaps with 11
(left-most element of the unsorted array).
Sorted Sublist | Unsorted Sublist | Least element in Unsorted list |
(10 ) |
(25, 11, 22, 64) | 25 |
Now repeat steps 1 to 3 until all the elements of the unsorted sublist are placed in the sorted sublist. See the below table.
Sorted sublist | Unsorted sublist | Least element in Unsorted list |
---|---|---|
() | (11, 25, 10, 22, 64) | 10 |
(10) | (25, 11, 22, 64) | 11 |
(10, 11) | (25, 22, 64) | 22 |
(10, 11, 22) | (25, 64) | 25 |
(10, 11, 22, 25) | (64) | 64 |
(10, 11, 22, 25, 64) | () |
Selection Sort example code:
Now let’s see the example code for the Selection Sort Algorithm using the C programming language.
#include <stdio.h> void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void selectionSort(int arr[], int array_size) { int i, j, min_idx; // One by one move boundary of unsorted Sublist for (i = 0; i < array_size-1; i++) { // Index of the minimum element in unsorted array // in beginning first element as minimum element min_idx = i; for (j = i+1; j < array_size; j++) { //compare unsorted element with minimum element if (arr[j] < arr[min_idx]) { min_idx = j; } } //minimum is placed in the front of the unsorted list. swap(&arr[min_idx], &arr[i]); } } //print array element void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { //input array int arr[] = {11, 25, 10, 22, 64}; //aray size int array_size = sizeof(arr)/sizeof(arr[0]); //selection sort algorithm selectionSort(arr, array_size); printf("Sorted array: \n"); printArray(arr, array_size); return 0; }
Output:
Selection Sort Complexity:
Time Complexity | |
---|---|
Best | O(n2 ) |
Worst | O(n2 ) |
Average | O(n2 ) |
Space Complexity | O(1) |
Advantages:
- Easy to implement.
- In-place sort (requires no additional storage space)
Disadvantages
- Doesn’t scale well: O(n2)
Recommended Articles for you:
- Bubble Sort Algorithm.
- Quickselect Algorithm.
- Merge Sort algorithm with example code.
- Quick Sort Algorithm with example code.
- Best programming laptop for programmers.
- How do you reverse an array in C?
- C program to find the Median of two sorted arrays of different sizes.
- Basics of the recursive function.
- C program to rearrange array such that even positioned are greater than odd.
- How to rotate an array left and right by a given number K?
- Why is it faster to process sorted array than an unsorted array?
- How to access 2d array in C?
- How to remove duplicates from a given array in C?
- Array interview questions.
- How to create dynamic array in C?
- How to pass an array as a parameter in C?