• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

Selection Sort in C with Explanation | Algorithm, Program and Time Complexity

Aniruddha Chaudhari/32796/4
C / C++CodeCSE SubjectData Structure

There are many sorting algorithms to sort the elements in the array. Some of the simple and widely used algorithms are as follows.

  • Bubble Sort
  • Quick Sort
  • Insertion Sort
  • Selection Sort

In this C programming tutorial, we see the program for selection sort in C with explanation in detail.

What is Selection Sort?

Selection sort is an algorithm where we keep finding the smallest element and then we order them in sequence.

Stepwise Explanation for Selection Sort Algorithm:

  1. Keep a pointer to the first element of the array (says i).
  2. Select the smallest element from the array.
  3. Replace the smallest element with the array element placed at position ‘i’.
  4. Increment ‘i’ to point it to next element in the array.
  5. Repeat step 2, 3 and 4 until ‘i’ reaches to the last element in an array.

Selection sort is the in-place sorting algorithm, Why?

Selection sort is the in-place sorting algorithm. It takes a constant amount of space and does not require any auxiliary data structure for sorting.  However, it uses very small amount of memory to replace the elements.

Selection Sort Program in C:

#include<stdio.h>

int main()
{
 int nArr[]={5,35,5,31,56}; 
 int nSize = sizeof(nArr)/sizeof(int);//5
 int nMin=0;
 int t=0, i=0, j=0;
 
 printf("\nGiven Array:");
 for(i=0;i<nSize;i++)
 {
 printf(" %d", nArr[i]);
 }
 
 //sort array using selection sort
 for(i=0; i<nSize-1 ;i++)
 {
 nMin=i;
 for(j=i+1; j<nSize;j++)
 {
 if(nArr[j]<nArr[nMin])
 nMin = j;
 }
 
 t=nArr[i];
 nArr[i]=nArr[nMin];
 nArr[nMin]=t;
 }

 printf("\n\nSorted Array:");
 
 for(i=0;i<nSize;i++)
 {
 printf(" %d", nArr[i]);
 }
 printf("\n");
 return 0;
}

Note: We have assigned elements to the array in the program itself. You can take the array elements as user input as well.

The output of a Program:

Given Array: 5 35 5 31 56
Sorted array: 5 5 31 35 56

Selection Sort in C with Explanation output

This program and algorithm sort the array in ascending order.

If you want to sort the array in descending order, (step 2 in the algorithm) find the largest element rather than the smallest element.

The time complexity of the Selection Sort algorithm:

If you look at steps 2, 3, 4 and 5 iterates ‘n’ number of times. (Where n is a number of elements in the array (array size).) . So iterations take O(n) time.

Within each iteration,  you have to find out smallest element in the array. It takes the complexity of O(n).

So the total complexity of the Selection sort algorithm is O(n)* O(n)  i.e. O(n^2).

Worst Case Complexity: O(n^2)

Best Case Complexity: O(n^2)

Average Case Complexity: O(n^2)

Here, all three complexity will be the same.

In the best case, we consider as the array is already sorted. But to find out the smallest element, we need to iterate and check for all the elements in the array. So the best complexity is the same a worst case complexity.

You can also check if the array is already sorted before applying selection sort. In the best case, it saves your program execution time.

Comparing with other sorting algorithms:

Selection sort is easiest to implement and to code than other sorting algorithms. But, it is not much efficient in terms of time complexity.

Advantages of this selection sort:

  • Easily understood.
  • Easiest to implement and to code.
  • No extra space is required (in-place sorting)

The drawback of selection sort:

  • It has very high time complexity. (O(n^2) in all three cases.)

Note: For most efficient algorithm as per time complexity, you can use heap or merge sort. They have O(n log(n)) time complexity.

This is all about Selection Sort in C with Explanation. If you have any doubt feel free to write in a comment.

Happy Programming!

algorithmCodecppsorting
Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Comments

  • Reply
    Patrik
    April 28, 2017 at 1:15 pm

    Very well explained. It is good to improve my knowledge. Please add content about other sorting algorithms as well.

    • Reply
      Aniruddha Chaudhari
      April 28, 2017 at 4:59 pm

      Hi Patrik,
      Thanks and happy as you find it useful.
      I am working on writing about other sorting algorithms. It will get live soon. Stay tuned!

  • Reply
    Noor Salim
    June 27, 2021 at 3:50 pm

    Why algorithm design and analysis are important in a research perspective.

    • Reply
      Aniruddha Chaudhari
      June 27, 2021 at 11:42 pm

      The algorithm is useful to understand the logic and solution to the problem. Analysis of the algorithm is useful to identify the complexity of the algorithm or to identify which algorithm is superior than others.

Leave a Reply Cancel reply

C Programming

  1. C- Introduction
  2. C- Compile & Execute Program
  3. C- Data Types
  4. C- if-else statement
  5. C- While, do-while, for loop
  6. C- Array
  7. C- Function (Types/Call)
  8. C- strlen() vs sizeof()
  9. C- Nested Switch Statement
  10. C- Recursion
  11. C- Dynamic Programming
  12. C- Storage Classes
  13. C- Creating Header File
  14. C- Null Pointer
  15. C- Stack and Queue
  16. C- Implement Stack using Array
  17. C- Implement Linked List in C
  18. C- File Handling
  19. C- Makefile Tutorial

Object Oriented Concepts in C++

  • C++: C vs OOPs Language
  • C++: Introduction to OOPs Concepts
  • C++: Inheritance

Sorting Algorithms

  • Different Types of Sorting Algo
  • Selection Sort
  • Bubble Sort
  • Quick Sort

Programming for Practice

  1. Online C/C++ Compiler

String Handling:

  1. Remove White Spaces from String
  2. Implement strstr Function in C
  3. Convert String to Int – atoi()
  4. Check if String is Palindrome
  5. Check if Two Strings are Anagram
  6. Split String in using strtok_r()
  7. Undefined reference to strrev

Array:

  1. Check if Array is Sorted

Bit Manipulation:

  1. Count Number of 1’s in Binary

Linked List:

  1. Reverse a Linked List Elements

Number System:

  1. Program to Find 2’s Complement
  2. Convert Decimal to Binary in C

Tricky Questions:

  1. Add Two Numbers without Operator
  2. Find Next Greater Number
  3. Swap values without temp variable
  4. Print 1 to 100 without Loop

Interview Coding Questions

  • 50+ Interview Coding Questions

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard