CS 222 01 Programming Assignment 05 – Chapter 05
Chapter 05/binarySearch.py
def binarySearch(alist, item): first = 0 last = len(alist) - 1 found = False compare = 0 while first <= last and not found: midpoint = (first + last) // 2 compare += 1 if alist[midpoint] == item: found = True else: if item < alist[midpoint]: last = midpoint - 1 else: first = midpoint + 1 return found, compare def main(): lyst = [] for x in range(1000000): lyst.append(x) found, compare = binarySearch(lyst, 1000001) print("is number in list", found) print("Comparisons", compare) main()
Chapter 05/bubbleSort.py
import random def bubbleSort(alist): for passnum in range(len(alist) - 1, 0, -1): for i in range(passnum): if alist[i] > alist[i + 1]: temp = alist[i] alist[i] = alist[i + 1] alist[i + 1] = temp def printList(alist): count = 0 for x in range(len(alist)): if count % 10 == 0: print() print("%4d" % alist[x], end = " ") count += 1 def main(): lyst = [] n = int(input("Enter number of values: ")) for i in range(n): lyst.append(i) random.shuffle(lyst) #print("List before sort") #printList(lyst) #print("\n\nList after sort") bubbleSort(lyst) #printList(lyst) main()
Chapter 05/hash.py
class HashTable: def __init__(self): self.size = 47 self.slots = [None] * self.size self.data = [None] * self.size def put(self, key, data): hashValue = self.hashFunction(key, len(self.slots)) if self.slots[hashValue] == None: self.slots[hashValue] = key self.data[hashValue] = data else: if self.slots[hashValue] == key: self.data[hashValue] = data # replace else: nextslot = self.rehash(hashValue, len(self.slots)) while self.slots[nextslot] != None and \ self.slots[nextslot] != key: print("newslot", self.slots[nextslot]) nextslot = self.rehash(nextslot, len(self.slots)) if self.slots[nextslot] == None: self.slots[nextslot] = key self.data[nextslot] = data else: self.data[nextslot] = data # replace def hashFunction(self, key, size): return key % size def rehash(self, oldhash, size): return (oldhash + 1) % size def get(self, key): startslot = self.hashFunction(key, len(self.slots)) data = None stop = False found = False position = startslot 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 def __getitem__(self, key): return self.get(key) def __setitem__(self, key, data): self.put(key, data) def main(): H = HashTable() H[54] = "cat" H[26] = "dog" H[93] = "lion" H[17] = "tiger" H[31] = "bird" H[44] = "cow" H[55] = "pig" H[20] = "chicken" print("After adding 8 items") print(H.slots) print("Hash 20:", H[20]) print("Hash 17:", H[17]) H[101] = "penguin" H[20] = "duck" print("Change Hash 20 from chicken to duck:", H[20]) print("Hash data") print(H.data) main()
Chapter 05/insertion.py
import random def insertionSort(alist): for index in range(1, len(alist)): currentvalue = alist[index] position = index while position > 0 and alist[position - 1] > currentvalue: alist[position] = alist[position - 1] position -= 1 alist[position] = currentvalue def main(): lyst = [] n = int(input("Enter number of values: ")) for i in range(n): num = random.randint(1, n * 10) while num in lyst: num = random.randint(1, n * 10) lyst.append(num) print("Ready to Sort") insertionSort(lyst) count = 0 for i in range(len(lyst)): if count % 10 == 0: print() count = 0 print(lyst[i], end = " ") count += 1 main()
Chapter 05/mergeSort.py
import random def mergeSort(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 def printList(alist): count = 0 for x in range(len(alist)): if count % 10 == 0: print() print("%4d" % alist[x], end = " ") count += 1 def main(): lyst = [] n = int(input("Enter number of values: ")) for i in range(n): lyst.append(i) random.shuffle(lyst) #print("List before sort") #printList(lyst) #print("Ready to Sort") mergeSort(lyst) printList(lyst) main()
Chapter 05/quickSort.py
import random 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 def printList(alist): count = 0 for x in range(len(alist)): if count % 10 == 0: print() print("%4d" % alist[x], end = " ") count += 1 def main(): lyst = [] n = int(input("Enter number of values: ")) for i in range(n): lyst.append(i) random.shuffle(lyst) #printList(lyst) #print("Ready to Sort") quickSort(lyst) printList(lyst) main()
Chapter 05/RecursiveBinarySearch.py
def binarySearch(alist, item, compare): if len(alist) == 0: return compare, False else: midpoint = len(alist) // 2 compare += 1 if alist[midpoint] == item: return compare, True else: if item < alist[midpoint]: return compare, binarySearch(alist[:midpoint], item, compare) else: return compare, binarySearch(alist[midpoint+1:], item, compare) def main(): lyst = [] compare = 0 for x in range(100): lyst.append(x) compare, found = binarySearch(lyst, 54, compare) print("is number in list", found) print("Comparisons", compare) main()
Chapter 05/selectionSort.py
import random def insertionSort(alist): for index in range(1, len(alist)): currentValue = alist[index] position = index while position > 0 and alist[position - 1] > currentValue: alist[position] = alist[position - 1] position -= 1 alist[position] = currentValue def printList(alist): count = 0 for x in range(len(alist)): if count % 10 == 0: print() print("%4d" % alist[x], end = " ") count += 1 def main(): lyst = [] n = int(input("Enter number of values: ")) for i in range(n): lyst.append(i) random.shuffle(lyst) #print("List before sort") #printList(lyst) #print("\n\nList after sort") insertionSort(lyst) #printList(lyst) main()
Chapter 05/sequentialSearch.py
import random import time def sequentialSearch(alist, item): pos = 0 found = False compare = 0 while pos < len(alist) and not found: compare += 1 if alist[pos] == item: found = True else: pos += 1 print(pos, alist[pos]) return found, compare def main(): lyst = [] num = int(input("How many? ")) look = int(input("What number are you looking for? ")) for x in range(num): lyst.append(x) random.shuffle(lyst) #random.shuffle(lyst) start = time.time() found, compare = sequentialSearch(lyst, look) #print("is number in list", found) end = time.time() print("Comparisons:", compare) print("Time:", end - start) main()
Chapter 05/shellSort.py
import random def shellSort(alist): sublistCount = len(alist) // 2 while sublistCount > 0: for startPosition in range(sublistCount): gapInsertionSort(alist, startPosition, sublistCount) sublistCount = sublistCount // 2 def gapInsertionSort(alist, start, gap): for i in range(start + gap, len(alist), gap): currentValue = alist[i] position = i while position >= gap and \ alist[position - gap] > currentValue: alist[position] = alist[position - gap] position = position - gap alist[position] = currentValue def printList(alist): count = 0 for x in range(len(alist)): if count % 10 == 0: print() print("%4d" % alist[x], end = " ") count += 1 def main(): lyst = [] n = int(input("Enter number of values: ")) for i in range(n): lyst.append(i) random.shuffle(lyst) #print("List before sort") #printList(lyst) #print("\n\nList after sort") shellSort(lyst) #printList(lyst) main()
Chapter 05/shortBubbleSort.py
import random def bubbleSort(alist): exchanges = True passnum = len(alist) - 1 while passnum > 0 and exchanges: exchanges = False for i in range(passnum): if alist[i] > alist[i + 1]: exchanges = True temp = alist[i] alist[i] = alist[i + 1] alist[i + 1] = temp passnum -= 1 def printList(alist): count = 0 for x in range(len(alist)): if count % 10 == 0: print() print("%4d" % alist[x], end = " ") count += 1 def main(): lyst = [] n = int(input("Enter number of values: ")) for i in range(n): lyst.append(i) #random.shuffle(lyst) #print("List before sort") #printList(lyst) #print("\n\nList after sort") bubbleSort(lyst) #printList(lyst) main()
Chapter 05/sortingTest.py
import random import time def shellSort(alist): sublistCount = len(alist) // 2 while sublistCount > 0: for startPosition in range(sublistCount): gapInsertionSort(alist, startPosition, sublistCount) #print("After increment of size", sublistCount, "the list is") #printList(alist) sublistCount = sublistCount // 2 def gapInsertionSort(alist, start, gap): for i in range(start + gap, len(alist), gap): currentValue = alist[i] position = i while position >= gap and \ alist[position - gap] > currentValue: alist[position] = alist[position - gap] position = position - gap alist[position] = currentValue def main(): lyst = [] for x in range(1000000): lyst.append(x) random.shuffle(lyst) start = time.time() lyst.sort() end = time.time() print("Time:", end - start) start = time.time() shellSort(lyst) end = time.time() print("Shell Time:", end - start) main()