Selection Sort in C

Problem Statement: Given an array of N integers, write a program to implement the Selection sorting algorithm.

Examples:

Example 1:
Input: N = 6, array[] = {13,46,24,52,20,9}
Output: 9,13,20,24,46,52
Explanation: After sorting the array is: 9, 13, 20, 24, 46, 52

Example 2:
Input: N=5, array[] = {5,4,3,2,1}
Output: 1,2,3,4,5
Explanation: After sorting the array is: 1, 2, 3, 4, 5

Solution:

DisclaimerDon’t jump directly to the solution, try it out yourself first.

Approach:

  • Find the minimum element in the unsorted array and swap it with the element at the beginning.
  • The inner loop selects the minimum element in the unsorted array .
  • In the below dry run, 

Blue color represents unsorted array elements

The yellow color represents the elements to be swapped in an unsorted array

The green color represents the sorted array elements

Code:

C Program

#include<stdio.h>

void selection_sort(int arr[], int n) {
  // selection sort
  int i,j;
  for (i = 0; i < n - 1; i++) {
    int mini = i;
    for (j = i + 1; j < n; j++) {
      if (arr[j] < arr[mini]) {
        mini = j;
      }
    }
    int temp = arr[mini];
    arr[mini] = arr[i];
    arr[i] = temp;
  }

  printf("After selection sort: \n");
  for (int i = 0; i < n; i++) {
    printf("%d ",arr[i]);
  }

}
int main() {
  int arr[] = {13,46,24,52,20,9};
  int n = sizeof(arr) / sizeof(arr[0]);
   printf("Before selection sort: \n");
   for (int i = 0; i < n; i++) {
    printf("%d ",arr[i]);
  }
  printf("\n");
  selection_sort(arr, n);
  return 0;
}

Output:

Before selection sort:
13 46 24 52 20 9
After selection sort:
9 13 20 24 46 52

Time Complexity: O(n^2) (nested for loops)

Space Complexity: O(1)

Special thanks to Subhrajit Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article

Reference: https://takeuforward.org/sorting/selection-sort-algorithm/