Sorting algorithms/Insertion sort: Difference between revisions

Content added Content deleted

Inline

@@ Line 89: / Line 89: @@
 ===Insertion sort with binary search===
+ def insertion_sort_bin(seq):
+     for i in range(1, len(seq)):
-<code>
+         key = seq[i]
-def insertion_sort_bin(seq):
+         # invariant: ``seq[:i]`` is sorted
-    for i in range(1, len(seq)):
-        # invariant: ``seq[:i]`` is sorted
+         # find the least `low' such that ``seq[low]`` is not less then `key'.
-        key = seq[i]
+         #   binary search in sorted sequence ``seq[low: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:
+                 low = middle + 1
-	  middle = (low + up) // 2
+	     else:
-          if seq[middle] < key:
+                 up = middle
-              low = middle + 1
+         # insert key at position ``low``
+         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>