Insertion Sort Algorithm
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
However, insertion sort provides several advantages:
1. Simple implementation: Jon Bentley shows a three-line c version, and a five-line optimized version
Efficient for (quite) small data sets, much like other quadratic sorting algorithmsAdaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each component in the input is no more than K places away from its sorted position
2. Stable; i.e., makes not change the relative order of components with equal keys
/**
* Created by gazollajunior on 09/04/16.
*/
fun <T:Comparable<T>> insertionsort(items:MutableList<T>):List<T>{
if (items.isEmpty()){
return items
}
for (count in 1..items.count() - 1){
val item = items[count]
var i = count
while (i>0 && item < items[i - 1]){
items[i] = items[i - 1]
i -= 1
}
items[i] = item
}
return items
}
fun main(args: Array<String>) {
val names = mutableListOf("John", "Tim", "Zack", "Daniel", "Adam")
println(names)
var ordered = insertionsort(names)
println(ordered)
}
