Selection Sort in C

July 26, 2020

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

Algorithm of selection  sort

Algorithm  SELECTION(A,N): This algorithm sorts the array A with N elements.

1-[loop]

Repeat Step 2 and 3 for K=0,1,2,..N-2:

2-Call MIN(A,K,N)

3-[Interchange A[K] and A[LOC].]

Set TEMP=A[K],A[K]=A[LOC] and

A[LOC]=TEMP.

[End of Step 1 loop]

4-Exit.

 

Code of Selection sort in C

// C program for implementation of selection sort  
#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[] = {5, 3, 1, 9, 8, 2, 4, 7}; 
  int size = sizeof(array)/sizeof(array[0]);

  printf("This is how array looks 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("This is how array looks after sorting: \n"); 
  display(array, size); 

return 0; 
}
// C program for implementation of selection sort  
#include <stdio.h>

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[] = {5, 3, 1, 9, 8, 2, 4, 7};  
    int size = sizeof(array)/sizeof(array[0]);

    printf("This is how array looks before sorting: \n");  
    display(array, size);

    selectionSort(array, size); 

    printf("This is how array looks after sorting: \n");  
    display(array, size); 

    return 0;  
}

Output

Output

This is how array looks before sorting:   
5 3 1 9 8 2 4 7
This is how array looks after sorting:
1 2 3 4 5 7 8 9

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)

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