1  
  2  
  3  """
  4  Like a hand of cards: maintains sorted left sub-array and repeatedly inserts into it
  5  O(n^2), in-place, stable
  6  """
  7  def insertion_sort(l: list) -> None:
  8      for i in range(1, len(l)):
  9          # Repeatedly shift elements rightward
 10          key = l[i]
 11          j = i - 1
 12          while j >= 0 and l[j] > key:
 13              l[j + 1] = l[j]
 14              j -= 1
 15          # Place element i
 16          l[j + 1] = key
 17  
 18  
 19  """
 20  Maintains sorted left sub-array, and repeatedly selects the minimum element from the unsorted
 21  sub-array to place at the end of the left sub-array
 22  O(n^2), in-place, not stable
 23  """
 24  def selection_sort(l: list) -> None:
 25      for i in range(len(l) - 1):
 26          # Find minimum element index in remaining sub-array
 27          min_i = i
 28          for j in range(i+1, len(l)):
 29              if l[j] < l[min_i]:
 30                  min_i = j
 31          # Swap min element with start of unsorted sub-array
 32          l[i], l[min_i] = l[min_i], l[i]
 33  
 34  """
 35  Merge two sorted lists in O(n) time. Requires O(n) extra space
 36  """
 37  def merge(a: list, b: list) -> list:
 38      a_i, b_i, c = 0, 0, []
 39  
 40      while a_i < len(a) and b_i < len(b):
 41          if a[a_i] <= b[b_i]:  # using '<=' here makes mergesort stable
 42              c.append(a[a_i])
 43              a_i += 1
 44          else:
 45              c.append(b[b_i])
 46              b_i += 1
 47  
 48      if a_i < len(a):
 49          c.extend(a[a_i:])
 50      elif b_i < len(b):
 51          c.extend(b[b_i:])
 52  
 53      return c
 54  
 55  """
 56  Recursively sorts left, right sub-arrays and then merges with
 57  linear merge sub-routine
 58  O(n*log(n)), not in-place, stable
 59  """
 60  def merge_sort(l: list) -> list:
 61      if len(l) <= 1:
 62          return l
 63      mid = len(l) // 2
 64      return merge(merge_sort(l[:mid]), merge_sort(l[mid:]))
 65  
 66  
 67  """
 68  Rearrange arr[lo...hi] in-place in linear time such that all elements
 69  less than pivot are left of it, and all elements greater than or equal to pivot
 70  are right of it.
 71  Return pivot index
 72  lo and hi are inclusive indices within which to partition
 73  """
 74  def partition(arr: list, lo: int, hi: int) -> int:
 75      pivot = arr[hi]  # arbitrarily choosing last element as pivot
 76      pivot_idx = hi
 77      hi -= 1
 78      # maintain arr[left of lo] < pivot, arr[right of hi] >= pivot
 79      while lo <= hi:
 80          if arr[lo] < pivot:
 81              lo += 1
 82          else:
 83              arr[lo], arr[hi] = arr[hi], arr[lo]
 84              hi -= 1
 85  
 86      arr[lo], arr[pivot_idx] = arr[pivot_idx], arr[lo]
 87      return lo
 88  
 89  
 90  """
 91  Partitions array, then recursively sorts left and right sub-arrays
 92  Expected O(n*log(n)), in-place, not stable
 93  """
 94  def quick_sort(arr: list, lo=None, hi=None) -> None:
 95      if lo is None:
 96          lo, hi = 0, len(arr) - 1
 97      if hi <= lo:
 98          return
 99      pivot_idx = partition(arr, lo, hi)
100      quick_sort(arr, lo, pivot_idx - 1)
101      quick_sort(arr, pivot_idx + 1, hi)
102  
103  
104  
105  def binary_search(arr: list, elt) -> int:
106      """
107      :param arr: A sorted array
108      :param elt: The element to search for
109      :return: The index of the target element. -1 if not present
110      If target element is present multiple times, returns one of these indices
111      """
112      lo, hi = 0, len(arr) - 1
113      while lo <= hi:
114          mid = (lo + hi) // 2
115          if arr[mid] == elt:
116              return mid
117          elif arr[mid] > elt:
118              hi = mid - 1
119          else:
120              lo = mid + 1
121  
122      return -1
123  
124  
125  
126  l = [4, 3, 2, 7, 8, 1, 5, 6]
127  # insertion_sort(l)
128  # selection_sort(l)
129  # print(merge_sort(l))
130  
131  quick_sort(l)
132  print(l)
133  
134  for i in range(10):
135      print(binary_search(l, i))