Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
(→{{header|Kotlin}}: Add Kotlin alternative solution) |
|||
| Line 3,398: | Line 3,398: | ||
Sorted: [1, 2, 3, 3, 4, 5, 7, 8, 9, 12, 17]</pre> |
Sorted: [1, 2, 3, 3, 4, 5, 7, 8, 9, 12, 17]</pre> |
||
===Alternative solution, optimized using binary search=== |
===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`) |
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 this function performs a stable sort (unlike the Java solution which uses `binarySearch`). 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"> |
<syntaxhighlight lang="kotlin"> |
||