Selection Sort Program in C

Last Updated on June 9, 2023 by Mayank Dham

Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element in an array and swapping it with the first element of the array. This process is repeated until the array is sorted. Selection sort is an in-place sorting algorithm, which means that it does not require any additional memory. It is a simple algorithm to implement, but it is not very efficient and can be slow for large arrays.

What is the Selection Sort?

In a selection sort, the lowest value of the unsorted array’s unsorted items is chosen in each pass and transferred to the appropriate place inside the array. The algorithm is the most straightforward. It is an algorithm for sorting data using in-place comparisons. The array is divided into two portions in this process, the first of which is sorted and the second of which is not. The sorted section of the array is initially empty, whereas the unsorted portion of the array includes the given array. The sorted part is on the left, while the unsorted part is on the right.

In a Selection sort program in C , the unsorted array’s first element is chosen from its smallest elements and given the top spot. The second-smallest element is then chosen and put in the second slot after that. The procedure is repeated until the full array has been sorted.

The selection sort’s average and worst-case complexity, where n is the number of items, is O(n2). This makes it unsuitable for huge data collection.

Selection Sort Algorithm

• Set min to the first location
• Search the minimum element in the array
• Assign the second element as min and exchange the first position in the array with the minimal value.
• Repeat the procedure up until an array is sorted.

Working of Selection sort program in C

Let’s take an array {20, 12, 23, 55,21}

• Set the first element of the array as a minimum.
  Minimum = 20
• Compare the minimum with the next element, if it is smaller than the minimum assign this element as the minimum. Do this till the end of the array.
  Comparing with 12 : 20 > 12 , minimum = 12
  Comparing with 23 : 12 < 23 , minimum = 12
  Comparing with 55 : 12 < 55 , minimum = 12
  Comparing with 21 : 12 < 21 , minimum = 12
• Place the minimum at the first position( index 0) of the array.
  Array = {12, 20,23, 55, 21}
• for the next iteration, start sorting from the first unsorted element i.e. the element next to where the minimum is placed.
  Array = {12, 20,23, 55, 21}
  Searching starts from 20, the next element where the minimum is placed.
  Iteration 2:
  Minimum = 20
  Comparing with 23: 20 < 23, minimum = 20
  Comparing with 55: 20 < 55, minimum = 20
  Comparing with 21: 20 < 21, minimum = 20
  Minimum in place no change,
  Array = {12, 20,23, 55, 21}
  Iteration 3:
  Minimum = 23.
  Comparing with 55 : 23 < 55 , minimum = 23
  Comparing with 21 : 23 > 21 , minimum = 21
  The minimum is moved to index = 2
  Array = {12, 20, 21, 55, 23}
  Iteration 4 :
  Minimum = 55
  Comparing with 23 : 23 < 55 , minimum = 23
  Minimum in moved to index 3 Array = {12, 20, 21, 23, 55}

Selection sort program in C

// Selection sort in C
#include <stdio.h>
// function to swap the the position of two elements
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}
void selectionSort(int array[], int size) {
  for (int step = 0; step < size - 1; step++) {
    int min_idx = step;
    for (int i = step + 1; i < size; i++) 
{
      // To sort in descending order, change > to < in this line.
      // Select the minimum element in each loop.
      if (array[i] < array[min_idx])
        min_idx = i;
    }
    // put min at the correct position
    swap(&array[min_idx], &array[step]);
  }
}
// function to print an array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}
// driver code
int main() {
  int data[] = {20, 12, 10, 15, 2};
  int size = sizeof(data) / sizeof(data[0]);
  selectionSort(data, size);
  printf("Sorted array in Acsending Order:\n");
  printArray(data, size);
}

Selection Sort Complexity :

Number of comparisons: (n – 1) + (n – 2) + (n – 3) + ….. + 1 = n(n – 1) / 2 nearly equals to n2..

Time Complexity = O(n2)

We may also evaluate complexity by counting the number of loops. Since there are two loops, n*n = n2 is the complexity.

Worst Case Complexity: O(n2) The worst case scenario is when we want to sort in ascending order but the array is arranged in descending order.

Best Case Complexity: In the best case, the array is already sorted, at which point the complexity is O(n2).

Average Case Complexity: O (n2)
It happens when the array’s items are arranged randomly (neither ascending nor descending).

Conclusion
Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element in an array and swapping it with the first element of the array. This process is repeated until the array is sorted. Selection sort is an in-place sorting algorithm, which means that it does not require any additional memory. It is a simple algorithm to implement, but it is not very efficient and can be slow for large arrays. Selection sort should only be used for small arrays or when efficiency is not a major concern.

Frequently Asked Questions

Q1. What are the advantages of selection sort?
Selection sort is a simple sorting algorithm that is easy to implement and understand. It is also an in-place sorting algorithm, which means that it does not require any additional memory.

Q2. What are the disadvantages of selection sort?
Selection sort is not very efficient. It has a quadratic time complexity, which means that its running time is proportional to the square of the number of elements in the array. It is also not a stable sorting algorithm, which means that it does not preserve the original order of equal elements.

Q3. When should selection sort be used?
Selection sort should only be used for small arrays or when efficiency is not a major concern. There are many other sorting algorithms that are more efficient than selection sort, such as merge sort and quick sort.