Sorting algorithms/Insertion sort: Difference between revisions
→{{header|Kotlin}}: Add Kotlin alternative solution
(→{{header|Kotlin}}: Add Kotlin alternative solution) |
|||
Line 3,365:
=={{header|Kotlin}}==
===Standard solution, using int array===
<syntaxhighlight lang="kotlin">fun insertionSort(array: IntArray) {
for (index in 1 until array.size) {
Line 3,396 ⟶ 3,397:
<pre>Unsorted: [5, 2, 3, 17, 12, 1, 8, 3, 4, 9, 7]
Sorted: [1, 2, 3, 3, 4, 5, 7, 8, 9, 12, 17]</pre>
===Alternative solution, optimized using binary search===
Similar concept to C++ solution. This solution uses a hand-written algorithm to find the upper bound as there is no Kotlin/Java equivalent to C++'s `std::upper_bound`. Thus (unlike the Java solution which uses `binarySearch`) the following function performs a stable sort. It uses `copyInto` which is a faster way of shifting the elements of an array before inserting an element, compared to assigning individual array elements in a loop.
<syntaxhighlight lang="kotlin">
fun <T : Comparable<T>> Array<T>.insertionSort() {
for (i in 1..lastIndex) {
val currentElement = this[i]
var low = 0
var high = i - 1
while (low <= high) {
val mid = low + (high - low) / 2
if (this[mid] <= currentElement)
low = mid + 1
else
high = mid - 1
}
copyInto(this, low + 1, low, i)
this[low] = currentElement
}
}
</syntaxhighlight>
=={{header|Ksh}}==
| |||