Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45
The Most Useful Guide to Learn Selection Sort Algorithm

The selection sort algorithm is a simple, yet effective sorting algorithm. A selection-based sorting algorithm is described as an in-place comparison-based algorithm that divides the list into two parts, the sorted part on the left and the unsorted part on the right. Initially, the sorted section is empty, and the unsorted section contains the entire list. When sorting a small list, selection sort can be used. 

In the selection sort, the cost of swapping is irrelevant, and all elements must be checked. The cost of writing to memory matters in selection sort, just as it does in flash memory (the number of writes/swaps is O(n) as opposed to O(n2) in bubble sort).

What Is a Selection Sort Algorithm?

  • Selection sort is an effective and efficient sort algorithm based on comparison operations.
  • It adds one element in each iteration.
  • You need to select the smallest element in the array and move it to the beginning of the array by swapping with the front element.
  • You can also accomplish this by selecting the most potent element and positioning it at the back end.
  • In each iteration, selection sort selects an element and places it in the appropriate position.

what-is-selection-sort.

Following the definition of the selection sort algorithm, you will now go over the working procedure of the selection sort algorithm in this tutorial.

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

How Does the Selection Sort Algorithm Work?

Selection sort works by taking the smallest element in an unsorted array and bringing it to the front. You’ll go through each item (from left to right) until you find the smallest one. The first item in the array is now sorted, while the rest of the array is unsorted.

  • As an example, consider the array depicted below.

working-of-selection-sort-algorithm.

  • The entire list is scanned sequentially for the first position in the sorted list. You search the whole list and find that 10 is the lowest value in the first position, where 15 is stored.

working-of-selection-sort-algorithm1.

  • As a result, you replaced 15 with 10. After one iteration, the number 10, which happens to be the lowest value on the list, appears at the top of the sorted list.

working-of-selection-sort2

  • You must begin by scanning the rest of the list linearly for the second position, where 30 is located.

working-of-selection-sort-algorithm4

  • You discovered that 15 is the second lowest value on the list and should be placed second. You must switch these values.

working-of-selection-sort-algorithm5.j

  • After two iterations, the two least values are positioned at the beginning in a sorted manner.

working-of-selection-sort-algorithm6.

The same procedure is followed for the remaining array items.

The following is a visual representation of the entire sorting process.

working-of-selection-sort-final

Moving forward in this tutorial, you will see an algorithm and its pseudocode after understanding the working procedure of a selection sort algorithm.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

Algorithm and Pseudocode of a Selection Sort Algorithm

Algorithm of the Selection Sort Algorithm

The selection sort algorithm is as follows:

Step 1: Set Min to location 0 in Step 1.

Step 2: Look for the smallest element on the list.

Step 3: Replace the value at location Min with a different value.

Step 4: Increase Min to point to the next element

Step 5: Continue until the list is sorted.

Pseudocode of Selection Sort Algorithm

The selection sort pseudocode is as follows:

function selection sort 

   array : array of items

   size : size of list

   for i = 1 to size - 1                                       

      minimum = i // set current element as minimum

      for j = i+1 to n // check the element to be minimum

         if array[j] < array[minimum] then

            minimum = j;

         end if

      end for

      if indexofMinimum != i then //swap the minimum element with the current element

         swap array[minimum] and array[i]

      end if

   end for

end function


You will now look at the performance of the selection sort algorithm in this tutorial.

The Complexity of Selection Sort Algorithm

The time complexity of the selection sort algorithm is:

  • The selection sort algorithm is made up of two nested loops.
  • It has an O (n2) time complexity due to the two nested loops.

Best Case Complexity occurs when there is no need for sorting, i.e., the array has already been sorted. The time complexity of selection sort in the best-case scenario is O. (n2).

Average Case Complexity occurs when the array elements are arranged in a jumbled order that is neither ascending nor descending correctly. The selection sort has an average case time complexity of O. (n2).

Worst-case complexity - Worst case occurs when array elements must be sorted in reverse order. Assume you need to sort the array elements in ascending order, but they are in descending order. Selection sort has a worst-case time complexity of O. (n2).

The space complexity of the selection sort algorithm is:

  • An in-place algorithm is a selection sort algorithm.
  • It performs all computations in the original array and does not use any other arrays.
  • As a result, the space complexity is O. (1).

You will now look at some applications of the selection sort algorithm in this tutorial.

Applications of Selection Sort Algorithm

The following are some applications of how to use selection sort:

  • Selection sort consistently outperforms bubble and gnome sort.
  • When memory writing is a costly operation, this can be useful.
  • In terms of the number of writes ((n) swaps versus O(n2) swaps), selection sort is preferable to insertion sort.
  • It almost always far outnumbers the number of writes made by cycle sort, even though cycle sort is theoretically optimal in terms of the number of writes.
  • This is important if writes are significantly more expensive than reads, as with EEPROM or Flash memory, where each write reduces the memory's lifespan.

Following an understanding of some applications of the selection sort algorithm, you will now look at code implementation in C.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Code Implementation of Selection Sort Algorithm

Code implementation of selection sort:

#include <stdio.h>  

#include <conio.h>

#include <stdlib.h>

void selection(int array[], int n)  

{  

    int i, j, minimum;  

    for (i = 0; i < n-1; i++) //Move one at a time unsorted subarray boundary

    {  

        minimum = i; //in an unsorted array, the minimum element         

        for (j = i+1; j < n; j++)  

        if (array[j] < array[minimum])  

            minimum = j;  

    int temp = array[minimum]; // Replace the first element with the minimum element.

    array[minimum] = array[i];  

    array[i] = temp;  

    }  

}  

void printArr(int array1[], int n) //function to print the array//

{  

    int i;  

    for (i = 0; i < n; i++)  

        printf("%d ", array1[i]);  

}  

int main()  

{  

    int array1[] = { 15, 30, 29, 14, 39, 11 };  

    int n = sizeof(array1) / sizeof(array1[0]);  

    printf(" An array before sorting: - \n");  

    printArr(array1, n);  

    selection(array1, n);  

    printf("\nAn Array after sorting- \n");    

    printArr(array1, n);  

    return 0;  

}  

Output

output-of-selection-sort-algorithm

With this, you have reached the end of this tutorial, and now you will sum up what you have learned so far in the selection sort algorithm tutorial.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

This tutorial taught you what a selection sort algorithm is and how it works with an example to help you understand it well. Following that, you looked at the algorithm and pseudo code for this algorithm and how it performed in each scenario (best-case, average-case, and worst-case) before moving on to its application and, finally, a practical demonstration of the selection sort algorithm in C.

If you want a more comprehensive study that goes beyond Data Structure and Algorithms and covers the most in-demand programming languages and skills today, Simplilearn’s Full Stack Web Development PG Program in collaboration with Caltech CTME is the course for you. It's time to go out and explore.

If you have any questions about this tutorial, please leave them in the comments section below so that our experts can answer them as soon as possible.

Please stay safe until then and follow the Simplilearn channel.

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.