Anonymous user
Sorting algorithms/Insertion sort: Difference between revisions
m
→{{header|C++}}
(Updated D entry) |
m (→{{header|C++}}) |
||
Line 240:
=={{header|C++}}==
Uses C++11. Compile with
Uses binary search via std::upper_bound() to find the insertion position in logarithmic time, then performs the insertion via std::rotate(), in linear time.▼
g++ -std=c++11 insertion.cpp
▲Uses binary search via std::upper_bound() to find the insertion position in logarithmic time
<lang cpp>#include <algorithm>
#include <iostream>
#include <iterator>
void insertion_sort(RandomAccessIterator begin, RandomAccessIterator end) {
}
}
int main() {
▲template<typename Iter>
int a[] = {100, 2, 56, 200, -52, 3, 99, 33, 177, -199};
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
▲ for (Iter i = beg; i != end; ++i)
std::cout << "\n";
▲ std::rotate(std::upper_bound(beg, i, *i), i, i+1);
}</lang>
Output:
<pre>
-199 -52 2 3 33 56 99 100 177 200
</pre>
=={{header|C sharp|C#}}==
| |||