Selection Sort in C

The Selection sort in C is a simple sorting algorithm used for sorting an array by repeatedly iterates. It first finds the smallest element from the unsorted list of elements, swaps with the first position element, finds the second smallest element, swaps with the second position element, this process continues till all the elements are sorted. This method based on the following principle:

1. Select the element with the least value.
2. Exchange it with the first element.
3. Then repeat the above-given operations with the remaining (n – 1) elements, then with (n – 2) elements, until only one element (the most considerable element) is left.

Suppose we want to sort an array A with N elements A[1], A[2],….., A[N] using selection sort in ascending order. The algorithm begins (Pass 1) by finding the smallest element’s location in the array of N elements and interchange it with element A[1]. This step places the smallest element in A[1] and leaves the rest of the array in unsorted order. Then in the next step (Pass 2), find the location of the smallest element in the subarray A[2], A[3], …..A[N] of size N-1. Interchange this smallest element with A[2], leaving the elements A[1], A[2] in order.
In general, in the K^th step (Pass K), find the location of the smallest element in the unsorted subarray A[K], A[K+ 1],…., A[N] of size N-K-1 and interchange this smallest element with A[K] so that elements A[1], A[2],……, A[K] are sorted. This process continues until the last step (Pass N-1), select the second largest element and swaps it with A[N-1], leaving the largest element at A[N].

Selection sorting is an in-place sorting algorithm, it does not require additional storage, but it requires auxiliary memory to store the data temporarily. The selection-sort algorithm has the same efficiency as the bubble-sort algorithm. 

The selection sort can utilize if memory space is limited. It’s because, unlike other sorting algorithms, selection sort doesn’t go about swapping elements until the array end, resulting in less temporary storage space used.

The Advantages & Disadvantages of selection sort

The main advantage of the selection sort is that it performs well on a small list. It is used to sort files with tremendous values and small keys. It is because the selection is based on keys and swaps only if necessary.

The selection sort’s primary disadvantage is its inefficiency when the input size increases, and its performance decreases than the insertion sort algorithm.

Why selection sort is unstable?

The selection sort is not a stable sorting algorithm, because it finds the smallest element from the unsorted list of elements and swaps it with the element at current position.

Suppose the array is
6 3 4 9 5 6 7
Let’s distinguish the two 6’s as 6(a) and 6(b) .

So our array is:
6(a) 4 5 6(b) 3 7 9

After iteration 1:

3 will be swapped with the first position element:

So our array becomes:
3 4 5 6(b) 6(a) 7 9

Our array is in sorted order, and we see that 6(a) comes before 6(b) in the initial array but not in the sorted array.

So we can see that the selection sort is not stable.

Example of Selection Sort

We have an array {7, 5, 2, 1,8} the smallest element in this array is 1. Then we replace 1 in the first place, and after that, the array looks like {1, 5, 2, 7, 8}. Now, we’ll iterate and finds the smallest element again. We see the next smallest element is 2, swaps it with the second position array and scanning the array and finally, we get the sorted array as [1,2,5,7,8].

Algorithm for Selection Sort:

START
 Step 1 → Set smallest to the beginning
 Step 2 → Search the smallest element in the array
 Step 3 → swap the first element with the smallest element.
 Step 4 → assign the second element as smallest.
 Step 5 → Repeatedly iterates until we get a sorted array.
STOP

Time Complexity of Selection Sort in C

In Selection sort, the algorithm requires a minimum number of swaps, and in the best case it takes ZERO (0) swaps when the input is in the sorted array-like 1,2,3,4, The best, average, and worst-case complexities of the selection algorithm are O(n²) for sorting n elements. The selection sort is both the worst and the average case quadratic and does not require additional memory.

Worst case condition.

Worst case condition of sorting algorithms is when data is sorted in the reverse order. In selection sort when data is sorted in reversed order, the total number of comparisons

(n – 1)+(n – 2)+ ··· + [n – (n – 1)] = n(n – 1)- [1 + 2 + ··· + (n – 1)]
= n((n-1)/2)
T(n) = O(n²)

Let us take a look at the code for the the programmatic implementation.

Selection sort program in C

// C program for implementation of selection sort
#include<stdio.h>
int main() {
 int array[100], size, i, j, position, temp;
 printf("Enter Number of Elements : ");
 scanf("%d", &size);
 printf("Enter %d Numbers : ", size);
 for (i = 0; i < size; i++)
  scanf("%d", &array[i]);
  for (i = 0; i < (size - 1); i++) {
   position = i;
   for (j = i + 1; j < size; j++) {
    if (array[position] > array[j])
      position = j;
   }
   if (position != i) {
     temp = array[i];
     array[i] = array[position];
     array[position] = temp;
   }
 }
 printf("Sorted list in ascending order:\n");
 for (i = 0; i < size; i++)
   printf("%d\t", array[i]);
   return 0;
}