Reviewed and fact-checked by Sayantoni Das
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.
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 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.
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
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.
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.
