Data Structures and Algorithms (Selection Sort Algorithm) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

Write an algorithm to perform selection sort in an array.

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.

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

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.

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

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

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

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

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

The same procedure is followed for the remaining array items.

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

Moving forward in this tutorial, you will see an algorithm and its pseudocode after understanding the working procedure 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

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

Tirthankar Pal
MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview
2 year PGDM (E-Business) from Welingkar, Mumbai
4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology
Google and Hubspot Certification
Brain Bench Certification in C++, VC++, Data Structure and Project Management
10 years of Experience in Software Development out of that 6 years 8 months in Wipro
Selected in Six World Class UK Universities:-
King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds