Selection Sort in C

March 23, 2022

What is Selection Sort in C

In this Sorting technique the list is divided into two parts. first one is left end and second one is right end .  The selection Sort is very  simple sorting algorithm.

Sorting
Time Complexity (Best)Ω(n2)
Time Complexity (Avg)Θ(n2)
Time Complexity (Worst)O(n2)
Space ComplexityO(1)

Steps for Selection Sort in C

There are following Step of selection sort algorithm.

  • Step 1-Select the smallest value in the list.
  • Step 2-Swap smallest value with the first element of the list.
  • Step 3-Again select the smallest value in the list (exclude first value).
  • Step 4- Repeat above step for (n-1) elements untill the list is sorted.

Implementation of Selection Sort

  • We have been given a unsorted array. which we’ll  make  a sorted array using selection sort. first of all  find the smallest value in the array and then swap smallest value with the starting value.
  • According to the below image,  8 is smallest value in this array so 8 is swapped with the first element that is 72.
  • Similarly, in the next iteration we’ll  find the next smallest value, excluding the starting value so in this array  10 is second smallest value, which is to be swapped with 50.
  • These iteration will continue until we have the largest element to the right most end, along with all the other elements in their correct position.
  • And then we can finally say that the given array is converted in sorted array.
Selection Sort in C with example– 1

Code of Selection sort in C

// C program for implementation of selection sort
// Time Complexity : O(N^2)
// Space Complexity : O(1)
// Best, Avg, Worst Cases : All of them O(N^2)
#include<stdio.h>

/* Display function to print values */
void display(int array[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++)
        printf("%d ",array[i]);
    
    printf("\n"); 
}

// The main function to drive other functions 
int main() 
{ 
    int array[] = {72, 50, 10, 44, 8, 20}; 
    int size = sizeof(array)/sizeof(array[0]);

    printf("Before sorting: \n"); 
    display(array, size);
    
    int i, j, min_idx,temp;  
  
    // Loop to iterate on array 
    for (i = 0; i < size-1; i++)  
    {  
        // Here we try to find the min element in array 
        min_idx = i;  
        for (j = i+1; j < size; j++){
            if (array[j] < array[min_idx])  
                min_idx = j;  
        }
        // Here we interchange the min element with first one              
        temp = array[min_idx];
        array[min_idx] = array[i]; 
        array[i] = temp;
    }
    printf("\nAfter sorting: \n"); 
    display(array, size); 

    return 0; 
}
// C program for implementation of selection sort
// Time Complexity : O(N^2)
// Space Complexity : O(1)
// Best, Avg, Worst Cases : All of them O(N^2)
// C program for implementation of selection sort  
#include<stdio.h>

// function to swap item using pointers
void swap(int *xp, int *yp)  
{  
    int temp = *xp;  
    *xp = *yp;  
    *yp = temp;  
}  

void selectionSort(int array[], int size)  
{  
    int i, j, min_idx;  

    // Loop to iterate on array 
    for (i = 0; i < size-1; i++)  
    {  
        // Here we try to find the min element in array 
        min_idx = i;  
        for (j = i+1; j < size; j++)
        {
            if (array[j] < array[min_idx])  
                min_idx = j;  
        }
        // Here we interchange the min element with first one  
        swap(&array[min_idx], &array[i]);  
    }  
}  

/* Display function to print values */
void display(int array[], int size)  
{  
    int i;  
    for (i=0; i < size; i++)
        printf("%d ",array[i]);

    printf("\n");  
}  

// The main function to drive other functions 
int main()  
{  
    int array[] = {72, 50, 10, 44, 8, 20};  
    int size = sizeof(array)/sizeof(array[0]);

    printf("Before sorting: \n");  
    display(array, size);

    selectionSort(array, size); 

    printf("\nAfter sorting: \n");  
    display(array, size); 

    return 0;  
}

Output

Before sorting: 
72 50 10 44 8 20

After sorting: 
8 10 20 44 50 72

Performance

The Selection Sort best and worst case scenarios both follow the time complexity format O(n^2) as the sorting operation involves two nested loops. The size of the array again affects the performance.[1]

Strengths

  • The arrangement of elements does not affect its performance.
  • Uses fewer operations, so where data movement is costly it is more economical

Weaknesses

  • The comparisons within unsorted arrays requires O(n^2) which is ideal where n is small
Insertion Sort Algorithm in C meme
Selection sort in C meme

Time Complexity
For Selection Sort

Best

Ω(n2)

Average

Θ(n2)

Worst

O(n2)

Space Complexity

O(1)

Quiz time

Quiz Time

Question 1. Array = [10, 11, 12, 13, 14, 15], the number of iterations bubble sort(without flag variable) and Selection sort would take –

  1. 5 and 5
  2. 5 and 4
  3. 4 and 4
  4. 6 and 6

(Cognizant – Mettl Test)

In bubble sort they are talking about passes, even though the question says iterations.

A bubble sort with n items takes (n-1) passes.

In selection sort also for n items its (n-1) passes.

Thus, 4 and 4 is answer

Option C

Question 2. Array = [10, 11, 12, 13, 14, 15], the number of iterations bubble sort(with flag variable) and Selection sort would take –

  1. 5 and 5
  2. 5 and 4
  3. 4 and 4
  4. 1 and 4

(Cognizant – Mettl Test)

In bubble sort they are talking about passes, even though the question says iterations.

A bubble sort with n items takes (n-1) passes. But, since the whole array is sorted, bubble sort will have just one pass to realize the array is sorted and abandon other passes

In selection sort also for n items its (n-1) passes, even though the array is sorted

Thus, 1 and 4 is answer

Option C

Question 3. What is the best case complexity of selection sort?

  1. O(nlogn)
  2. O(logn)
  3. O(n)
  4. O(n2)

(Wipro – AMCAT Test)

In selection sort all cases the time complexity is : O(N^2)

Explanation: The best, average and worst case complexities of selection sort is O(n2).
(n-1) + (n-2) + (n-3) + …. + 1 = (n(n-1))/2 ~ (n2)/2.

Question 4. Array[] = {72, 50, 10, 44, 8, 20} how would the array look like in iteration 4

  1. 8, 10, 44, 20, 72, 50
  2. 8, 10, 20, 44, 72, 50
  3. 8, 10, 20, 44, 50, 72
  4. None

(Wipro – AMCAT Test)

Answer : B

The array will look like – 8, 10, 20, 44, 72, 50

Check image

Selection Sort in C with example– 1

Sorting

Sorting algorithms are easy to learn but are really important for college semester exams and companies offering package between 3 – 6 LPA would ask direct searching questions in online test/ interviews.

Data Structures and Algorithm Learn Sorting