Selection sort is another simple sorting algorithm that works by repeatedly finding the minimum (or maximum) element from the unsorted part of the array or list and placing it at the beginning of the sorted part. The algorithm divides the array or list into two parts: the sorted part and the unsorted part. The sorted part starts at the beginning of the array or list and grows by one element with each iteration of the algorithm. The unsorted part is the remaining part of the array or list that has not yet been sorted.
fun selectionSort(arr: IntArray) {
for (i in 0 until arr.size - 1) {
var minIndex = i
for (j in i + 1 until arr.size) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
if (minIndex != i) {
val temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
}
}The selectionSort function takes an array of integers arr and sorts it in place using the selection sort algorithm.
The function uses a for loop to iterate over each element of the array, starting from the first element (i.e., index 0). The minIndex variable represents the index of the minimum element in the unsorted part of the array. The function then uses another for loop to search for the minimum element in the unsorted part of the array. If the current element being examined is less than the current minimum element, the minIndex variable is updated to the index of the current element.
Once the minimum element in the unsorted part of the array is found, the function swaps it with the first element in the unsorted part of the array (i.e., the element at index i). This places the minimum element in its correct position at the beginning of the sorted part of the array.
This process continues until all elements in the array are sorted.
Selection sort has a time complexity of O(n^2) in the worst case, where n is the number of elements in the array. This means that the time it takes to sort an array using selection sort increases quadratically with the size of the array. However, selection sort can be very efficient for small arrays or partially sorted arrays, and it has the advantage of requiring only O(1) additional space for the sort operation.
fun main() {
val arr = intArrayOf(20, 15, 81, 12, 6)
val index = selectionSort(arr)
for(i in 1 until arr.size)
println(arr[i])
}
fun selectionSort(arr: IntArray) {
for (i in 0 until arr.size - 1) {
var minIndex = i
for (j in i + 1 until arr.size) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
if (minIndex != i) {
val temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
}
}