Selection sort in C. In this article, we will cover the basics of selection sort, its implementation in C, and discuss its performance and applications.
Table of Contents
Selection sort
Selection sort is a straight forward yet efficient algorithm for sorting an array or list of elements. Unlike more complex sorting algorithms, selection sort is easy to understand and implement, Making it an excellent educational tool for new programmers. It operates on a very simple principle- Divide the list into two parts the sorted part at the beginning and the unsorted part at the end. Then repeatedly select the smallest (or largest, depending on sorting order) element from the unsorted action and move it to the end of the sorted section.
Selection Sort Program in C
Implementing Selection sort in C involves very clear steps. The process starts with the outer loop, which iterates over each element of the array except the last one. The inner loop then finds the minimum element in the unsorted section of the array. after finding the minimum element it is swapped with the first unsorted element, effectively growing the sorted section of the array by one element.
Selection Sort C Program
#include <stdio.h>
void selectionSort(int array[], int n)
{
int i, j, minindex, temp;
for (i = 0; i < n - 1; i++)
{
minindex = i;
for (j = i + 1; j < n; j++)
{
if (array[j] < array[minindex])
{
minindex = j;
}
}
temp = array[minindex];
array[minindex] = array[i];
array[i] = temp;
}
}
void main()
{
int array[] = {90, 68, 8, 4, 2, 67, 23, 56, 78, 34, 56};
int n = sizeof(array) / sizeof(array[0]);
printf("Array before sorting\n");
for (int i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
selectionSort(array, n);
printf("\nArray after sorting\n");
for (int i = 0; i < n; i++)
{
printf("%d ", array[i]);
}
}
Output
Selection Sort Complexity
Selection sort has a time complexity of O(n^2) where n is the number of items being sorted. This time complexity carries because, for each element, the algorithm must search for the remaining elements to find the minimum or maximum.
Despite this, the space complexity of the selection sort is an advantage, requiring only O(1) additional storage space. This makes it an in-place sorting algorithm, ideal for situations where memory use is a concern.
Advantages of Selection Sort
- Selection sort in conceptually simple and easy to understand.
- Selection sort performs the sorting operation without requiring any additional storage.
- Selection sort performance remains consistent regardless of the initial order of elements.
- Selection sort minimizes the number of memory writes(swaps).
Applications of Selection sort
Selection sort is best suited for small data sets or situations where memory is highly constrained. Its predictable behavior and ease of implementation make it an excellent choice for introductory programming courses to demonstrate basic sorting algorithms. However, for large data sets or applications requiring optimal performance, a more advanced sorting algorithm would be preferable.
Happy Coding & Learning
5 thoughts on “Selection Sort in C”