Selection Sorting
Selection Sort is a straightforward sorting algorithm that relies on comparisons. Splitting the input list into a sorted sub-list and an unsorted sub-list is its main concept. The unsorted sub-list has every entry in it, while the sorted sub-list is initially empty.
The smallest (or largest, depending on the sorting order) entry from the unsorted sub-list is repeatedly chosen by the algorithm and moved to the end of the sorted sub-list. Until the sorted sub-list has every member in the intended order and the unsorted sub-list is empty, this process is repeated.
Working of Selection Sorting Algorithm
Finding the smallest or largest member in an unsorted array and replacing it with the first or last unsorted element, respectively, is how the selection sort algorithm operates. Until the entire array is sorted, these steps are repeated.
The selection sort algorithm's steps are as follows:
Step 1: Make the first component the smallest.
Step 2: Compare the second element to the minimum.
Step 3: Assign the second element as the minimum if it is smaller.
Step 4: For every element in the array, repeat the comparison procedure.
Step 5: Put the minimum at the top of the unsorted list at the end of each iteration.
Step 6:Continue steps 1 through 5 until every element is positioned correctly.
Example of Selection Sorting Algorithm
Let's use selection sort to arrange the array [65, 26, 12, 22, 11]:
- Find the array's smallest element by starting with the first element, 65. Since 11 is the smallest, replace it with 65. [26, 12, 22, 65, 11].
- Locate the smallest element in the remaining section before moving on to element 26.
- Since 12 is the smallest, replace it with 26. 11–12, 26–22, 65.
- Locate the smallest element in the remaining section before moving on to element 26. Since 22 is the smallest, replace it with 26.
- 11–12, 22–26, 65 Elements 26 and 27 are already in the proper positions. The final part, number 65, is already positioned correctly.
- The array is currently
Advantages of Selection Sort
- It is simple to comprehend and use, which makes it perfect for teaching fundamental sorting ideas.
- Just a constant O(1) additional memory space is needed.
- In comparison to several other common algorithms, it uses fewer swaps (or memory writes). When it comes to memory writes, only cycle sort is superior. As a result, when memory writes are expensive, it may be easy to choose an algorithm.
- Selection sort id slower than algorithm like Quick sort or Merge Sort because of its O(n^2) time complexity.
- Does not keep equal components in their proper relative order.
- Selection sort is not reliable since it does not maintain the relative order.
Complexity of Selection Sort Algorithm
1. Time Complexity
O(n2) is the time complexity because there are two nested loops:
One loop to choose an array element one at a time = O(n) An additional loop to compare that element with each other element in the array = O(n) Thus, total complexity is equal to O(n) * O(n) = O(n*n) = O(n2).
2. Auxiliary Space
O(1) because temporary variables are the only memory usage.
