text: ##############################################
  class HashTable(object):
      
      def __init__(self,size):
          
          # Set up size and slots and data
          self.size = size
          self.slots = [None] * self.size
          self.data = [None] * self.size
          
      def put(self,key,data):
          #Note, we'll only use integer keys for ease of use with the Hash Function
          
          # Get the hash value
          hashvalue = self.hashfunction(key,len(self.slots))
  
          # If Slot is Empty
          if self.slots[hashvalue] == None:
              self.slots[hashvalue] = key
              self.data[hashvalue] = data
          
          else:
              
              # If key already exists, replace old value
              if self.slots[hashvalue] == key:
                  self.data[hashvalue] = data  
              
              # Otherwise, find the next available slot
              else:
                  
                  nextslot = self.rehash(hashvalue,len(self.slots))
                  
                  # Get to the next slot
                  while self.slots[nextslot] != None and self.slots[nextslot] != key:
                      nextslot = self.rehash(nextslot,len(self.slots))
                  
                  # Set new key, if NONE
                  if self.slots[nextslot] == None:
                      self.slots[nextslot]=key
                      self.data[nextslot]=data
                      
                  # Otherwise replace old value
                  else:
                      self.data[nextslot] = data 
  
      def hashfunction(self,key,size):
          # Remainder Method
          return key%size
  
      def rehash(self,oldhash,size):
          # For finding next possible positions
          return (oldhash+1)%size
      
      
      def get(self,key):
          
          # Getting items given a key
          
          # Set up variables for our search
          startslot = self.hashfunction(key,len(self.slots))
          data = None
          stop = False
          found = False
          position = startslot
          
          # Until we discern that its not empty or found (and haven't stopped yet)
          while self.slots[position] != None and not found and not stop:
              
              if self.slots[position] == key:
                  found = True
                  data = self.data[position]
                  
              else:
                  position=self.rehash(position,len(self.slots))
                  if position == startslot:
                      
                      stop = True
          return data
  
      # Special Methods for use with Python indexing
      def __getitem__(self,key):
          return self.get(key)
  
      def __setitem__(self,key,data):
          self.put(key,data)
  
  
  ##############################################
  #Implementation of Binary Search
  # list must already be sorted!
  
  def binary_search(arr,ele):
      
      # First and last index values
      first = 0
      last = len(arr) - 1
      
      found = False
      
      
      while first <= last and not found:
          
          mid = (first+last)/2 # or // for Python 3
          
          # Match found
          if arr[mid] == ele:
              found = True
          
          # Set new midpoints up or down depending on comparison
          else:
              # Set down
              if ele < arr[mid]:
                  last = mid -1
              # Set up 
              else:
                  first = mid + 1
                  
      return found
  
  # list must already be sorted!
  arr = [1,2,3,4,5,6,7,8,9,10]
  
  #Recursive Version of Binary Search
  def rec_bin_search(arr,ele):
      
      # Base Case!
      if len(arr) == 0:
          return False
      
      # Recursive Case
      else:
          
          mid = len(arr)/2
          
          # If match found
          if arr[mid]==ele:
              return True
          
          else:
              
              # Call again on second half
              if ele<arr[mid]:
                  return rec_bin_search(arr[:mid],ele)
              
              # Or call on first half
              else:
                  return rec_bin_search(arr[mid+1:],ele)
  
  
  ##############################################
  #Implementation of a Bubble Sort
  def bubble_sort(arr):
      # For every element (arranged backwards)
      for n in range(len(arr)-1,0,-1):
          #
          for k in range(n):
              # If we come to a point to switch
              if arr[k]>arr[k+1]:
                  temp = arr[k]
                  arr[k] = arr[k+1]
                  arr[k+1] = temp
  
  
  # O(n^2)
  
  # Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
  # 
  # Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
  # 
  # Auxiliary Space: O(1)
  
  
  ##############################################
  #Implementation of Selection Sort
  def selection_sort(arr):
      
      # For every slot in array
      for fillslot in range(len(arr)-1,0,-1):
          positionOfMax=0
          
          # For every set of 0 to fillslot+1
          for location in range(1,fillslot+1):
              # Set maximum's location
              if arr[location]>arr[positionOfMax]:
                  positionOfMax = location
  
          temp = arr[fillslot]
          arr[fillslot] = arr[positionOfMax]
          arr[positionOfMax] = temp
  #Time Complexity: O(n^2) 
  
  ##############################################
  #Implementation of Insertion Sort
  
  def insertion_sort(arr):
      
      # For every index in array
      for i in range(1,len(arr)):
          
          # Set current values and position
          currentvalue = arr[i]
          position = i
          
          # Sorted Sublist
          while position>0 and arr[position-1]>currentvalue:
              
              arr[position]=arr[position-1]
              position = position-1
  
          arr[position]=currentvalue
  
  
  #Time Complexity: O(n^2) 
  
  
  ##############################################
  #Implementation of Shell Sort
  
  def shell_sort(arr):
      sublistcount = len(arr)/2
      
      # While we still have sub lists
      while sublistcount > 0:
          for start in range(sublistcount):
              # Use a gap insertion
              gap_insertion_sort(arr,start,sublistcount)
  
        
  
          sublistcount = sublistcount / 2
  
  def gap_insertion_sort(arr,start,gap):
      for i in range(start+gap,len(arr),gap):
  
          currentvalue = arr[i]
          position = i
  
          # Using the Gap
          while position>=gap and arr[position-gap]>currentvalue:
              arr[position]=arr[position-gap]
              position = position-gap
          
          # Set current value
          arr[position]=currentvalue
  
  #Time Complexity: O(n^2) 
  
  ##############################################
  #Implementation of Merge Sort
  def merge_sort(arr):
      
      if len(arr)>1:
          mid = len(arr)/2
          lefthalf = arr[:mid]
          righthalf = arr[mid:]
  
          merge_sort(lefthalf)
          merge_sort(righthalf)
  
          i=0
          j=0
          k=0
          while i < len(lefthalf) and j < len(righthalf):
              if lefthalf[i] < righthalf[j]:
                  arr[k]=lefthalf[i]
                  i=i+1
              else:
                  arr[k]=righthalf[j]
                  j=j+1
              k=k+1
  
          while i < len(lefthalf):
              arr[k]=lefthalf[i]
              i=i+1
              k=k+1
  
          while j < len(righthalf):
              arr[k]=righthalf[j]
              j=j+1
              k=k+1
  
  # Time Complexity( Best, Average, Worst): O(n log(n))
  #Space Complexity: O(n)
  ##############################################
  #Implementation of Quick Sort
  def quick_sort(arr):
      
      quick_sort_help(arr,0,len(arr)-1)
  
  def quick_sort_help(arr,first,last):
      
      if first<last:
          
  
          splitpoint = partition(arr,first,last)
  
          quick_sort_help(arr,first,splitpoint-1)
          quick_sort_help(arr,splitpoint+1,last)
  
  
  def partition(arr,first,last):
      
      pivotvalue = arr[first]
  
      leftmark = first+1
      rightmark = last
  
      done = False
      while not done:
  
          while leftmark <= rightmark and arr[leftmark] <= pivotvalue:
              leftmark = leftmark + 1
  
          while arr[rightmark] >= pivotvalue and rightmark >= leftmark:
              rightmark = rightmark -1
  
          if rightmark < leftmark:
              done = True
          else:
              temp = arr[leftmark]
              arr[leftmark] = arr[rightmark]
              arr[rightmark] = temp
  
      temp = arr[first]
      arr[first] = arr[rightmark]
      arr[rightmark] = temp
  
  
      return rightmark
  
  # Time Complexity: Worst : O(n^2)    (Best, Average): O(n log(n))
  #Space Complexity: O(log(n))
  
  
  
  ##############################################
  #Heap Sort
  # Python program for implementation of heap Sort
   
  # To heapify subtree rooted at index i.
  # n is size of heap
  def heapify(arr, n, i):
      largest = i  # Initialize largest as root
      l = 2 * i + 1     # left = 2*i + 1
      r = 2 * i + 2     # right = 2*i + 2
   
      # See if left child of root exists and is
      # greater than root
      if l < n and arr[i] < arr[l]:
          largest = l
   
      # See if right child of root exists and is
      # greater than root
      if r < n and arr[largest] < arr[r]:
          largest = r
   
      # Change root, if needed
      if largest != i:
          arr[i],arr[largest] = arr[largest],arr[i]  # swap
   
          # Heapify the root.
          heapify(arr, n, largest)
   
  # The main function to sort an array of given size
  def heapSort(arr):
      n = len(arr)
   
      # Build a maxheap.
      for i in range(n, -1, -1):
          heapify(arr, n, i)
   
      # One by one extract elements
      for i in range(n-1, 0, -1):
          arr[i], arr[0] = arr[0], arr[i]   # swap
          heapify(arr, i, 0)
          
          
  # Time Complexity( Best, Average, Worst): O(n log(n))
  #Space Complexity: O(1)
  