Sorting algorithms/Insertion sort: Difference between revisions
Content added Content deleted
(→{{header|C++}}: Using std::upper_bound keeps this sort stable in the presence of equal keys and may be faster.) |
(Undo revision 101335 by 208.80.119.67 (talk) — For this task, I think it is more to the point to have the algorithm) |
||
Line 943: | Line 943: | ||
l[j+1] = key</lang> |
l[j+1] = key</lang> |
||
===Insertion sort with binary search=== |
===Insertion sort with binary search=== |
||
<lang python> |
<lang python>def insertion_sort_bin(seq): |
||
def insertion_sort_bin(seq): |
|||
for i in range(1, len(seq)): |
for i in range(1, len(seq)): |
||
key = seq[i] |
|||
# invariant: ``seq[:i]`` is sorted |
|||
# find the least `low' such that ``seq[low]`` is not less then `key'. |
|||
# Binary search in sorted sequence ``seq[low:up]``: |
|||
low, up = 0, i |
|||
while up > low: |
|||
middle = (low + up) // 2 |
|||
if seq[middle] < key: |
|||
low = middle + 1 |
|||
else: |
|||
up = middle |
|||
# insert key at position ``low`` |
|||
seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]</lang> |
|||
=={{header|R}}== |
=={{header|R}}== |
||
Direct translation of pseudocode. |
Direct translation of pseudocode. |