It is an easy sorting algorithm. We must split the list into two domains before applying the selection sorting method. The sorted part will be on the left side and the unorganised or unsorted segment at the right end.
Basically, the selection sort algorithm organises a list of an array by constantly discovering the minimum component (assuming ascending order) from the unsorted part and placing it at the starting point. The algorithm is very simple and popular. However, it is not appropriate for extensive data sets.
Table of Contents
- Working of Selection Sort Algorithm
- Selection Sort Algorithm
- Time Complexity of Selection Sort Algorithm
- Space Complexity of Selection Sort Algorithm
Working of Selection Sort Algorithm
As an instance, consider the array that is shown below.
The entire list is successively scanned for the first place in the organised and sorted array. We search the entire list and discover that 9 is the lowest number at the first slot, where 13 is now kept.
Therefore, we change 13 to 9. 9 appears at the top of the sorted list after one iteration since it is the list’s minimal value.
We begin linearly scanning the rest of the list for position 2, where 32 sits.
13 is the second-lowest figure on the list, so it should be second, according to our calculations. These values are switched.
The two least values are positioned first in a sorted order after two iterations.
The remaining of the array’s entries are treated using the same procedure.
Here is a visual representation of the complete sorting procedure:
Let’s now explore some programming concepts related to selection sorting.
Selection Sort Algorithm
- Stage1: Place MIN at position 0.
- Stage2: Look for the least common element in the list.
- Stage3: Switch at location MIN with value
- Stage4: Increase MIN to indicate the following element.
- Stage5: Once the list is sorted, repeat.
Time Complexity of Selection Sort Algorithm
| Case | Time Complexity of Selection Sort |
|---|---|
| Best Case | O(n2) |
| Average Case | O(n2) |
| Worst Case | O(n2) |
Space Complexity of Selection Sort Algorithm
| Space Complexity of Selection Sort Algorithm | O(1) |
|---|
Practice Problems:
Q1. Which of the following sorting algorithms has the lowest worst-case complexity?
A) Merge Sort
B) Bubble Sort
C) Quick Sort
D) Selection Sort
Q2. Consider the following array.
| 23 | 32 | 45 | 69 | 72 | 73 | 89 | 97 |
|---|
Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?
A) Insertion Sort
B) Quick Sort using the last element as pivot
C) Merge Sort
D) Selection Sort
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
