Selection Sort Program in C

We shall talk about the Selection sort algorithm in this article. The selecting sort’s operational process is very straightforward. Students who might have to answer a question on selection sort in their exams will find this material to be both highly informative and engaging. So it’s crucial to have a conversation about it.

What is the Selection Sort?

In a selection sort, the unsorted array’s unsorted elements’ lowest value is picked out in each pass and moved to the proper location inside the array. The algorithm is also the simplest. It is an algorithm for in-place comparison sorting. In this procedure, the array is split into two sections, the first of which is sorted and the second of which is unsorted. The array’s sorted portion starts off empty, while its unsorted portion contains the specified array. On the left is the sorted portion, while on the right is the unsorted portion.

In a selection sort, 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?

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).

Other C Programs

C Program for Binary Search
C Program to Add Two Numbers
C Program to Calculate Percentage of 5 Subjects
C Program to Convert Binary Number to Decimal Number
C Program to Convert Celsius to Fahrenheit
C Program to Convert Infix to Postfix
C Program to Find Area of Circle
C Program to Find Roots of Quadratic Equation
C program to Reverse a Linked List
C program to reverse a number
Ascending Order Program in C
Menu Driven Program For All Operations On Doubly Linked List in C
C Program for Armstrong Number
C Program For Merge Sort For Linked Lists
C program for performing Bubble sort on Linked List
Hello World Program in C
Perfect Number Program in C
Leap Year Program in C
Odd Even Program in C