Suppose you are a company owner and want to give your employees a bonus on the new year. Here, you have already sorted data of the employee’s salary; then you can use it and add the increment value as per the positions of the employees. How is the selection sort algorithm used here?
Well, the employee’s salary data is already sorted (salaries divided as per the position). That is why they just have to compare the salary, find out the smallest value, place it at suitable positions, and add the incremental amount.
Find it confusing?
Let’s understand more details about the selection sort in the upcoming paragraphs. But before that, let’s know what the selection sorting algorithm is.
What is the selection sort algorithm?
This is one of the sorting algorithms in which the smallest element of an unsorted array gets selected and lists it in a single iteration. And then place it at the starting of the unsorted list. This process continues until the array or list does not get sorted.
The selection sort algorithm has two subarrays within the particular array.
- The already subarray.
- The remaining and unsorted subarray.
Finally, the minimum or the smaller element from the unsorted subarray will be selected and moved forward to the sorted subarrays in each selection sort iteration.
Key point: When is the selection sort algorithm useful?
Selection sort is always a good option when the data is already sorted. Moreover, it is quite useful when you are running with the memory space. (https://www.cantravelwilltravel.com/) It is due to a selection sort that does not go with the swapping method. That is why it results in less and temporary storage space. |
How does selection sort work?
Here, I will define the process of how the selection sort works.
- Set the first element of the list or array as the minimum.
- Compare the minimum number with the adjacent or second element. If the number is found smaller than the selected smaller number, then assign the element set to minimum.
Compare the minimum element with the next (that is, third) element. If it is smaller, then assign the third to the smallest number; otherwise, do nothing. This process will continue till the last element of the array.
- Once the iteration is completed, the minimum places in the unsorted list’s front.
- Here, you need to keep in mind that the indexing of the unsorted element will start from the beginning. And step 1 to 3 will repeat till the elements place at the correct position.
Selection sort algorithm with flow chart
selectionSort(arr, size)
repeat (size – 1) times
setting the first unsorted item or element as minimum
for every unsorted element
if element < currentMinimum
set it (element) as new minimum
swap minimum element with first unsorted index position
end selectionSort
Let’s take an example of selection sort in Java
For your convenience, we have explained select sort with the help of Java programming
// Selection sort in Java
import java.util.Arrays;
class SelectionSort {
void selectionSort(int arr[]) {
int size = arr.length;
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i < size; i++) {
// For sorting the elements in descending order,
// modify > to <.
// Choose the minimum element from
// the array in each loop.
if (arr[i] < arr[min_idx]) {
min_idx = i;
}
}
// putting minimum at the correct position
int temp = arr[step];
arr[step] = arr[min_idx];
arr[min_idx] = temp;
}
}
// driver code
public static void main(String args[]) {
int[] data = { 30, 22, 20, 25, 12 };
SelectionSort ss = new SelectionSort();
ss.selectionSort(data);
System.out.println("The Sorted Array: ");
System.out.println(Arrays.toString(data));
}
}
Output:
The Sorted Array: [12, 20, 22, 25, 30]
What about the complexity of the selection sort algorithm?
Below, we have mentioned the table that defines the different complexity factors, such as the time complexity of selection sort.
Time complexity:
Worst | O(n^2) |
Average | O(n^2) |
Best | O(n^2) |
Stability:
No
Space Complexity
O(1)
What are the applications of selection sort?
The selection sort is useful in the cases:
- when the swapping cost does not matter
- writing cost to the memory matters such as flash memory (number of swaps/writes O(n) in comparison to O (n^2) of the bubble sort)
- the smaller list need to be sort
- checking the elements of a list or array is compulsory
Bonus Point:
When to avoid using the selection sort algorithm? There are three main situations when you must avoid using the selection sort algorithms. And these are: |
Conclusion
Selection Sort is a too easy algorithm to appear in your next coding interview with Microsoft or Google. You just need to know some of the key points about selection sort.
These are as follows:
- Starting with the first element, choose one element from the array.
- Sequentially compare it to all other entries in the array.
- Swap their locations if an element discovers to be smaller than the presently chosen element.
Before going on to the next member in the array, make sure you find the right place for the selected element.
Apart from this, I want to recommend you to please solve each sorting iteration on paper if you truly want to learn sorting algorithms. Only attempt to code it and validate each stage of your paper answer once you have solved it successfully on paper.
Frequently Asked Questions
Why is selection sort used?
You can use it for the scenarios:
When the array isn’t ordered in any way.
When we’re working with a limited amount of RAM.
In the case when the sorting solution is required.
What is the principle of selection sort?
The Selection sort algorithm works by locating the smallest or largest element in an unsorted array. And then place it in the right location in a sorted array. Assume you need to sort the array A = [7, 5, 4, 2] in ascending order. Using selection sort, it finally looks like A = [2, 4, 5, 7].