Anonymous user
Sorting algorithms/Insertion sort: Difference between revisions
Sorting algorithms/Insertion sort (view source)
Revision as of 02:43, 20 December 2007
, 16 years ago→Insertion sort with binary search: fix formatting
(→Insertion sort with binary search: fix formatting) |
(→Insertion sort with binary search: fix formatting) |
||
Line 89:
===Insertion sort with binary search===
def insertion_sort_bin(seq):▼
for i in range(1, len(seq)):▼
▲def insertion_sort_bin(seq):
# invariant: ``seq[:i]`` is sorted
▲ for i in range(1, len(seq)):
#
while up > low:
middle = (low + up) // 2
# insert key at position ``low
seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]▼
return seq▼
▲ up = middle
▲ seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]
▲ return seq
|