Insertion sort
Algorithms #algorithms #sortingPick element at current index and then compare it with previous indices until you find the right position of the element.
If the element at picked index is already greater than the previous index then move on, otherwise compare it with all previous elements until you find element greater than this one.
- Best case will happen if array is already sorted.
- Worst case will happen if array is sorted in reverse order
Best case time complexity is O(n) and worst case is O(n2)
fun main() {
val arr = intArrayOf(2, 1, 10, 0, 2)
println(arr.contentToString())
insertionSort(arr) // sort
println("sorted: ${arr.contentToString()}")
}
fun insertionSort(arr: IntArray) {
for (i in 1 until arr.size) {
val current = arr[i]
var j = i.dec()
while (j >= 0 && arr[j] > current) {
arr[j.inc()] = arr[j--]
}
arr[j.inc()] = current
}
}