Data Structures and Algorithms in Python

binarySearch.py

def binarySearch(alist, item):
	first = 0
	last = len(alist) - 1
	found = False

	while first <= last and not found:
		midpoint = (first + last) // 2
		if alist[midpoint] == item:
			found = True
		else:
			if item < alist[midpoint]:
				last = midpoint - 1
			else:
				first = midpoint + 1

		return found


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))

binarySearchTrees.py

class TreeNode:
    def __init__(self,key,val,left=None,right=None,parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self

    def isRightChild(self):
        return self.parent and self.parent.rightChild == self

    def isRoot(self):
        return not self.parent

    def isLeaf(self):
        return not (self.rightChild or self.leftChild)

    def hasAnyChildren(self):
        return self.rightChild or self.leftChild

    def hasBothChildren(self):
        return self.rightChild and self.leftChild

    def replaceNodeData(self,key,value,lc,rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self


class BinarySearchTree:

    def __init__(self):
        self.root = None
        self.size = 0

    def length(self):
        return self.size

    def __len__(self):
        return self.size

    def put(self,key,val):
        if self.root:
            self._put(key,val,self.root)
        else:
            self.root = TreeNode(key,val)
        self.size = self.size + 1

    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                   self._put(key,val,currentNode.leftChild)
            else:
                   currentNode.leftChild = TreeNode(key,val,parent=currentNode)
        else:
            if currentNode.hasRightChild():
                   self._put(key,val,currentNode.rightChild)
            else:
                   currentNode.rightChild = TreeNode(key,val,parent=currentNode)

    def __setitem__(self,k,v):
       self.put(k,v)

    def get(self,key):
       if self.root:
           res = self._get(key,self.root)
           if res:
                  return res.payload
           else:
                  return None
       else:
           return None

    def _get(self,key,currentNode):
       if not currentNode:
           return None
       elif currentNode.key == key:
           return currentNode
       elif key < currentNode.key:
           return self._get(key,currentNode.leftChild)
       else:
           return self._get(key,currentNode.rightChild)

    def __getitem__(self,key):
       return self.get(key)

    def __contains__(self,key):
       if self._get(key,self.root):
           return True
       else:
           return False

    def delete(self,key):
      if self.size > 1:
         nodeToRemove = self._get(key,self.root)
         if nodeToRemove:
             self.remove(nodeToRemove)
             self.size = self.size-1
         else:
             raise KeyError('Error, key not in tree')
      elif self.size == 1 and self.root.key == key:
         self.root = None
         self.size = self.size - 1
      else:
         raise KeyError('Error, key not in tree')

    def __delitem__(self,key):
       self.delete(key)

    def spliceOut(self):
       if self.isLeaf():
           if self.isLeftChild():
                  self.parent.leftChild = None
           else:
                  self.parent.rightChild = None
       elif self.hasAnyChildren():
           if self.hasLeftChild():
                  if self.isLeftChild():
                     self.parent.leftChild = self.leftChild
                  else:
                     self.parent.rightChild = self.leftChild
                  self.leftChild.parent = self.parent
           else:
                  if self.isLeftChild():
                     self.parent.leftChild = self.rightChild
                  else:
                     self.parent.rightChild = self.rightChild
                  self.rightChild.parent = self.parent

    def findSuccessor(self):
      succ = None
      if self.hasRightChild():
          succ = self.rightChild.findMin()
      else:
          if self.parent:
                 if self.isLeftChild():
                     succ = self.parent
                 else:
                     self.parent.rightChild = None
                     succ = self.parent.findSuccessor()
                     self.parent.rightChild = self
      return succ

    def findMin(self):
      current = self
      while current.hasLeftChild():
          current = current.leftChild
      return current

    def remove(self,currentNode):
         if currentNode.isLeaf(): #leaf
           if currentNode == currentNode.parent.leftChild:
               currentNode.parent.leftChild = None
           else:
               currentNode.parent.rightChild = None
         elif currentNode.hasBothChildren(): #interior
           succ = currentNode.findSuccessor()
           succ.spliceOut()
           currentNode.key = succ.key
           currentNode.payload = succ.payload

         else: # this node has one child
           if currentNode.hasLeftChild():
             if currentNode.isLeftChild():
                 currentNode.leftChild.parent = currentNode.parent
                 currentNode.parent.leftChild = currentNode.leftChild
             elif currentNode.isRightChild():
                 currentNode.leftChild.parent = currentNode.parent
                 currentNode.parent.rightChild = currentNode.leftChild
             else:
                 currentNode.replaceNodeData(currentNode.leftChild.key,
                                    currentNode.leftChild.payload,
                                    currentNode.leftChild.leftChild,
                                    currentNode.leftChild.rightChild)
           else:
             if currentNode.isLeftChild():
                 currentNode.rightChild.parent = currentNode.parent
                 currentNode.parent.leftChild = currentNode.rightChild
             elif currentNode.isRightChild():
                 currentNode.rightChild.parent = currentNode.parent
                 currentNode.parent.rightChild = currentNode.rightChild
             else:
                 currentNode.replaceNodeData(currentNode.rightChild.key,
                                    currentNode.rightChild.payload,
                                    currentNode.rightChild.leftChild,
                                    currentNode.rightChild.rightChild)




mytree = BinarySearchTree()
mytree[3]="red"
mytree[4]="blue"
mytree[6]="yellow"
mytree[2]="at"

print(mytree[6])
print(mytree[2])

BinaryTree.py

def BinaryTree(r):
	return [r, [], []]

def insertLeft(root,newBranch):
	t = root.pop(1)
	if len(t) > 1:
		root.insert(1, [newBranch,t,[]])
	else:
		root.insert(1, [newBranch, [], []])
	return root

def insertRight(root,newBranch):
	t = root.pop(2)
	if len(t) > 1:
		root.insert(2, [newBranch, [], t])
	else:
		root.insert(2, [newBranch, [], []])
	return root

def getRootVal(root):
	return root[0]

def setRootVal(root,newVal):
    root[0] = newVal

def getLeftChild(root):
	return root[1]

def getRightChild(root):
	return root[2]

r = BinaryTree(3)
print r
insertLeft(r,4)
print r

bubbleSort.py

def bubbleSort(alist):
	i = 0
	n = len(alist)
	print n
	for _ in range(n):
		bubb(i,n,alist)
		n -= 1


def bubb(i,n,alist):
	while i < (n - 1):
		if alist[i] > alist[i+1]:
			temp = alist[i]
			alist[i] = alist[i+1]
			alist[i+1] = temp
		i += 1




alist = [54,26,93,17,77,31,44,55,20]
bubbleSort(alist)
print(alist)

insertionSort.py

def insertionSort(alist):
	i = 1
	n = len(alist)
	while i < (n):
		print alist[i]
		reverseBubble(i,alist)
		i += 1
		print alist

def reverseBubble(i,alist):
	for _ in range(i,0,-1):
			if alist[i] < alist[i-1]:
				temp = alist[i-1]
				alist[i-1] = alist[i]
				alist[i] = temp
				i -= 1



alist = [54,26,93,17,77,31,44,55,20]
insertionSort(alist)
print(alist)

mergeSort.py

def mergeSort(alist):
	print("Splitting ",alist)
	if len(alist) > 1:
		mid = len(alist) // 2
		lefthalf = alist[:mid]
		righthalf = alist[mid:]

		mergeSort(lefthalf)
		mergeSort(righthalf)

		i=0
		j=0
		k=0
		while i < len(lefthalf) and j < len(righthalf):
			if lefthalf[i] < righthalf[j]:
				alist[k] = lefthalf[i]
				i=i+1
			else:
				alist[k] = righthalf[j]
				j=j+1
			k=k+1

		while i<len(lefthalf):
			alist[k]=lefthalf[i]
			i=i+1
			k=k+1
		
		while j<len(righthalf):
			alist[k]=righthalf[j]
			j=j+1
			k=k+1
	print("Merging ",alist)



alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

quickSort.py

def quickSort(alist):
	quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
	if first < last:
		
		splitpoint = partition(alist,first,last)

		quickSortHelper(alist,first,splitpoint-1)
		quickSortHelper(alist,splitpoint+1,last)

def partition(alist,first,last):
	pivotvalue = alist[first]

	leftmark = first+1
	rightmark = last

	done = False
	while not done:
		
		while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
			leftmark = leftmark+1

		while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
			rightmark = rightmark-1

		if rightmark < leftmark:
			done = True
		else:
			temp = alist[leftmark]
			alist[leftmark] = alist[rightmark]
			alist[rightmark] = temp

	temp = alist[first]
	alist[first] = alist[rightmark]
	alist[rightmark] = temp

	return rightmark



alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)

selectionSort.py

def selectionSort(alist):
	i = 0
	n = len(alist)
	for _ in range(n):
		select(i,n,alist)
		n -= 1



def select(i,n,alist):
	biggest = alist[0]
	index = 0
	while i < (n):
		if biggest < alist[i]:
			biggest = alist[i]
			index = i
		i += 1
	temp = alist[n-1]
	alist[n-1] = biggest
	alist[index] = temp
	print biggest
		



alist = [54,26,93,17,77,31,44,55,20]
selectionSort(alist)
print(alist)

sequentialSearch.py

def sequentialSearch(alist, item):
	i = 0
	n = len(alist)
	while i < n:
		if  alist[i] == item:
			return i+1
		i += 1


testlist = [1, 2, 32, 8, 17, 19, 42, 13, 0]
print(sequentialSearch(testlist, 3))
print(sequentialSearch(testlist, 13))

shellSort.py

def shellSort(alist):
	n = len(alist)
	while n > 0:
		n = n // 2
		print n
		i = 0
		while i < (len(alist) - n):
			if alist[i] > alist[i+n]:
				temp = alist[i+n]
				alist[i+n] = alist[i]
				alist[i] = temp
			i += 1

alist = [54,26,93,17,77,31,44,55,20]
shellSort(alist)
print(alist)