Insertion sort is a simple sorting algorithm that works by building the final sorted array or list one element at a time, by inserting each unsorted element into its proper position within the sorted array or list. The algorithm maintains a sub-array of sorted elements and inserts each new element into its proper position within the sub-array, shifting the other elements to make room for the new element.
fun insertionSort(arr: IntArray) {
for (i in 1 until arr.size) {
val key = arr[i]
var j = i - 1
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
}The insertionSort function takes an array of integers arr and sorts it in place using the insertion sort algorithm.
The function uses a for loop to iterate over each element of the array starting from the second element (i.e., index 1). The key variable represents the current element being sorted, and the j variable represents the index of the previous element in the sub-array of sorted elements.
The function then uses a while loop to shift the elements of the sub-array to the right until it finds the proper position for the key element. The j variable is decremented until it reaches the start of the array or until it finds an element that is less than or equal to the key element. Each element in the sub-array that is greater than the key element is shifted one position to the right to make room for the key element.
Once the proper position for the key element is found, the function inserts the key element into the sub-array at the correct position. This process continues until all elements in the array are sorted.
Insertion 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 insertion sort increases quadratically with the size of the array. However, insertion sort can be very efficient for small arrays or partially sorted arrays.
Complete code with example
fun main() {
val arr = intArrayOf(20, 15, 81, 12, 6)
val index = insertionSort(arr)
for(i in 1 until arr.size)
println(arr[i])
}
fun insertionSort(arr: IntArray) {
for (i in 1 until arr.size) {
val key = arr[i]
var j = i - 1
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]
j--
}
arr[j + 1] = key
}
}