package sort
/**
* This method implements the Generic Selection Sort
*
* @param array The array to be sorted
* Sorts the array by repeatedly finding the minimum element from unsorted part and putting in the beginning
*
* Worst-case performance O(n^2)
* Best-case performance O(n^2)
* Average performance O(n^2)
* Worst-case space complexity O(1)
**/
fun <T : Comparable<T>> selectionSort(array: Array<T>) {
val length = array.size - 1
for (i in 0..length) {
var idx = i
for (j in i + 1..length) {
if (array[j] < array[idx]) {
idx = j
}
}
swapElements(array, i, idx)
}
}
Given an unsorted array of n elements, write a function to sort the array
O(n^2)
Worst case performance
O(n^2)
Best-case performance
O(n^2)
Average performance
O(1)
Worst case
arr[] = {80, 10, 40, 30}
Indexes: 0 1 2 3
1. Index = 0
Select the minimum number from the array (between index 0-3), ie, 10
2. Swap 10 and 80 (arr[0])
3. The array now is {10, 80, 40, 30}
4. Index = 1
Select the minimum number from the array (between index 1-3), ie, 30
5. Swap 30 and 80 (arr[1])
6. The array now is {10, 30, 40, 80}
7. Index = 2
Select the minimum number from the array (between index 2-3), ie, 40
8. Swap 40 and 40 (arr[2])
9. The array now is {10, 30, 40, 80}
The array is now sorted.
A video explaining the Selection Sort Algorithm