Jump to content

Sorting algorithms/Insertion sort: Difference between revisions

Sorting algorithms/Insertion sort (view source)

Revision as of 02:43, 20 December 2007

7 bytes added ,  16 years ago
→‎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)):▼
<code>
upkey = middleseq[i]▼
▲def insertion_sort_bin(seq):
# invariant: ``seq[:i]`` is sorted
▲ for i in range(1, len(seq)):
# invariant:find the least `low' such that ``seq[:ilow]`` is sorted not less then `key'.
key =# binary search in sorted sequence ``seq[ilow:up]``:
## low, up = 0, i
while up > low:
# find the least `low' such that ``seq[low]`` is not less then `key'.
middle = (low + up) // 2
# Binary search in sorted sequence ``seq[low:up]``:
low, up = 0, i if seq[middle] < key:
while up > low: = middle + 1
middle = (low + up) // 2else:
if seq[middle] < key: up = middle
# insert key at position ``low = middle + 1 ``
seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]▼
else:
return seq▼
▲ up = middle
##
# insert key at position ``low``
▲ seq[:] = seq[:low] + [key] + seq[low:i] + seq[i + 1:]
▲ return seq
</code>
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/42696"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information