Finished 4 and 5

4 files changed, 760 insertions, 0 deletions

diff --git a/hw4/__pycache__/assignment_lists_sortingandsearching_f22.cpython-310.pyc b/hw4/__pycache__/assignment_lists_sortingandsearching_f22.cpython-310.pyc
new file mode 100644
index 0000000..3bfec39
--- /dev/null
+++ b/hw4/__pycache__/assignment_lists_sortingandsearching_f22.cpython-310.pyc
diff --git a/hw4/__pycache__/bintest.cpython-310.pyc b/hw4/__pycache__/bintest.cpython-310.pyc
new file mode 100644
index 0000000..52c8672
--- /dev/null
+++ b/hw4/__pycache__/bintest.cpython-310.pyc
diff --git a/hw4/assignment_lists_sortingandsearching_f22.py b/hw4/assignment_lists_sortingandsearching_f22.py
new file mode 100644
index 0000000..ea131e3
--- /dev/null
+++ b/hw4/assignment_lists_sortingandsearching_f22.py
@@ -0,0 +1,571 @@
+# -*- coding: utf-8 -*-
+"""assignment-lists-sortingAndSearching_f22.ipynb
+
+Automatically generated by Colaboratory.
+
+Original file is located at
+    https://colab.research.google.com/drive/1Ra4cQV_Fn1TwDr-EzF2VlzM3Pnk752PA
+"""
+
+
+
+"""### Doubly Linked List
+
+We have previously developed a doubly linked list in an object oriented way. A proper implementation is found below, but feel free to use the code you wrote instead of mine.
+
+The code needs to be extended to have Class functions that will search for values and also will sort the values.
+
+## Constructing a Doubly Linked List
+
+The **Node** and **Doubly Linked List** class implementations are given:
+"""
+
+class Node(object):
+    """Doubly linked node which stores an object"""
+
+    def __init__(self, element, next_node=None, previous_node=None):
+        # The underscores are to prevent overwriting the variables if inherited and prevents access from outside of scope
+        self.__element = element
+        self.__next_node = next_node
+        self.__previous_node = previous_node
+
+    def get_element(self):
+        """Returns the element stored in this node"""
+        return self.__element
+
+    def get_previous(self):
+        """Returns the previous linked node"""
+        return self.__previous_node
+
+    def get_next(self):
+        """Returns the next linked node"""
+        return self.__next_node
+
+    def set_element(self, element):
+        """Sets the element stored in this node"""
+        self.__element = element
+
+    def set_previous(self, previous_node):
+        """Sets the previous linked node"""
+        self.__previous_node = previous_node
+
+    def set_next(self, next_node):
+        """Sets the next linked node"""
+        self.__next_node = next_node
+
+    def __gt__(self, node):
+        if self.get_element() > node.get_element():
+            return True
+        return False
+
+    def __ge__(self, node):
+        if node.get_element() <= self.get_element():
+            return True
+        return False
+
+    def __str__(self):
+        return str(self.__element)
+
+class DoublyLinkedList(object):
+    """Doubly linked node data structure"""
+
+    def __init__(self):
+        self.__size = 0
+        self.__header = Node('Header')
+        self.__trailer = Node('Trailer')
+        self.__header.set_next(self.__trailer)
+        self.__trailer.set_previous(self.__header)
+        self.__current = None
+
+    def __repr__(self):
+        if not self.is_empty():
+            out = f'('
+            for node in self:
+                out += f"({node.get_element()}), "
+            out = out[:-2]
+            out += ')'
+        else:
+            out = 'Empty List'
+        return out
+    def __iter__(self):
+        self.__current = None
+        return self
+
+    def __next__(self):
+        """Standard python iterator method"""
+        if self.is_empty() or self.__current == self.__trailer:
+            raise StopIteration()
+        elif self.__current is None:
+            self.__current = self.__header
+        self.__current = self.__current.get_next()
+        if self.__current != self.__trailer:
+            return self.__current
+        else:
+            raise StopIteration()
+
+    def map(self, function):
+        """Run function on every element in the list"""
+        for node in self:
+            if node != self.__trailer and node != self.__header:
+                node.set_element(function(node.get_element()))
+
+    def size(self):
+        """Returns the number of elements in the list"""
+        return self.__size
+
+    def is_empty(self):
+        """Returns the number of elements in the list"""
+        return self.__size == 0
+
+    def get_first(self):
+        """Get the first element of the list"""
+        if self.is_empty():
+            raise Exception("List is empty")
+        else:
+            return self.__header.get_next()
+
+    def get_last(self):
+        """Get the last element of the list"""
+        if self.is_empty():
+            raise Exception("List is empty")
+        else:
+            return self.__trailer.get_previous()
+
+    def get_previous(self, node):
+        """Returns the node before the given node"""
+        if node == self.__header:
+            raise Exception("Cannot get the element before the header of this list")
+        else:
+            return node.get_previous()
+
+    def get_next(self, node):
+        """Returns the node after the given node"""
+        if node == self.__trailer:
+            raise Exception("Cannot get the element after the trailer of this list")
+        else:
+            return node.get_next()
+
+    def add_before(self, new, existing):
+        """Insert the new before existing"""
+        previous_existing = self.get_previous(existing)
+        new.set_previous(previous_existing)
+        new.set_next(existing)
+        existing.set_previous(new)
+        previous_existing.set_next(new)
+        self.__size += 1
+
+    def add_after(self, new, existing):
+        """Insert the new after existing"""
+        next_existing = self.get_next(existing)
+        new.set_previous(existing)
+        new.set_next(next_existing)
+        existing.set_next(new)
+        next_existing.set_previous(new)
+        self.__size += 1
+
+    def add_first(self, new):
+        """Insert the node at the head of the list"""
+        self.add_after(new, self.__header)
+
+    def add_last(self, new):
+        """Insert the node at the tail of the list"""
+        self.add_before(new, self.__trailer)
+
+    def remove(self, node):
+        """Removes the given node from the list"""
+        before = self.get_previous(node)
+        after = self.get_next(node)
+        before.set_next(after)
+        after.set_previous(before)
+        node.set_next(None)
+        node.set_previous(None)
+        self.__size -= 1
+        return node
+
+    def __getitem__(self, index):
+        """
+        Move to a given index in the list
+        I copied this over from the last assignment to make things easier
+        """
+        assert index < self.__size
+        if index < (self.__size // 2):
+            pos = self.get_next(self.__header)
+            for _ in range(index):
+                pos = self.get_next(pos)
+        else:
+            pos = self.__trailer
+            for _ in range(self.__size - index):
+                pos = self.get_previous(pos)
+
+        return pos
+
+    def swap(self, target, moving):
+        """
+        prev -> moving - > target
+
+        >>> dll = DoublyLinkedList()
+        >>> dll.add_last(Node('a'))
+        >>> b = Node('b')
+        >>> dll.add_last(b)
+        >>> c = Node('c')
+        >>> dll.add_last(c)
+        >>> dll
+        ((a), (b), (c))
+        >>> dll.swap(b, c)
+        >>> dll
+        ((a), (c), (b))
+        """
+        if moving == self.__trailer or moving == self.__header:
+            raise Exception("You cannot move the header or trailer")
+        pm = moving.get_previous()
+        am = moving.get_next()
+        pm.set_next(am)
+        am.set_previous(pm)
+        prev = target.get_previous()
+        prev.set_next(moving)
+        moving.set_previous(prev)
+        moving.set_next(target)
+        target.set_previous(moving)
+
+
+    def swap_forward(self, node):
+        """
+        before: prev -> node -> next
+        after:  prev -> next -> node
+
+        >>> dll = DoublyLinkedList()
+        >>> dll.add_first(Node('a'))
+        >>> dll.add_first(Node('b'))
+        >>> c = Node('c')
+        >>> dll.add_first(c)
+        >>> dll.swap_forward(c)
+        >>> dll
+        ((b), (c), (a))
+        """
+        self.swap(node, node.get_next())
+
+    def swap_backward(self, node):
+        """
+        before: prev -> node -> next
+        after:  next -> prev -> next
+
+        >>> dll = DoublyLinkedList()
+        >>> dll.add_last(Node('a'))
+        >>> dll.add_last(Node('b'))
+        >>> c = Node('c')
+        >>> dll.add_last(c)
+        >>> dll.swap_backward(c)
+        >>> dll
+        ((a), (c), (b))
+        """
+        self.swap(node.get_previous(), node)
+
+    def replace(self, new, existing):
+        """
+        before: prev -> existing -> next
+        after: prev -> new -> next
+        """
+        self.add_before(new, existing)
+        self.remove(existing)
+
+    def sequential_search(self,value):
+        """Finds the value in the list and returns the node"""
+        for node in self:
+            if node.get_element() == value:
+                return node
+        return None
+
+    def binary_search(self,value):
+        """Implementation of a binary search for a value,
+            also returns the node"""
+        #HINT: REQUIRES THE LIST TO BE SORTED!
+        max = self.size()
+        index = max // 2
+        val = self[index]
+        while val.get_element() != value:
+            if index <= 0 or index >= self.size() - 1:
+                return None
+            elif val.get_element() > value:
+                max = index
+                index = index // 2
+                val = self[index]
+            else:
+                index += (max - index) // 2
+                val = self[index]
+        return val
+
+    def bubble_sort(self):
+        """
+        >>> dll = DoublyLinkedList()
+        >>> [ dll.add_first(Node(i)) for i in range(20) ]
+        >>> dll.bubble_sort()
+        >>> dll
+        """
+        for i in range(self.size()):
+            n = self.get_first()
+            for j in range(self.size()-i):
+                if n.get_next() != self.__trailer:
+                    if n > n.get_next():
+                        self.swap_forward(n)
+                    else:
+                        n = n.get_next()
+
+    def selection_sort(self):
+        """
+        Sort a list using insertion sort
+        >>> dll = DoublyLinkedList()
+        >>> [ dll.add_first(Node(i)) for i in range(20) ]
+        >>> dll.insertion_sort()
+        >>> dll
+        """
+        # Start at the beginning and move through every element
+        head = self.__header
+        while head != self.get_last():
+            min = head.get_next()
+            cmp = min
+            # Find the minimum value in the rest of the unsorted list
+            while cmp != self.__trailer:
+                if cmp <= min:
+                    min = cmp
+                cmp = cmp.get_next()
+            # This prevents elements from linking to themselves
+            if head.get_next() != min:
+                self.swap(head.get_next(), min)
+            head = min
+
+    def insertion_sort(self):
+        """
+        Sort a list using insertion sort
+        >>> dll = DoublyLinkedList()
+        >>> [ dll.add_first(Node(i)) for i in range(20) ]
+        >>> dll.insertion_sort()
+        >>> dll
+        """
+        # Get the first element to compare to others
+        cmphead = self.get_first()
+        cmp = cmphead.get_next()
+        # Move through all elements
+        while cmp != self.__trailer:
+            # Switch the cmphead if the compared node is bigger
+            if cmphead < cmp:
+                cmphead = cmp
+                cmp = cmphead.get_next()
+                continue
+            # Move the cmp node to its right place
+            prev = cmp.get_previous()
+            while prev != self.__header:
+                if prev > cmp:
+                    prev = prev.get_previous()
+                    self.swap_backward(cmp)
+                else:
+                    break
+            cmp = cmphead.get_next()
+
+    def shell_sort(self):
+        gap = self.size() // 2 # This should give a good gap size
+        while 1 < gap:
+            j = 0
+            while j - gap < 0: # This prevents running out of elements
+                if self[j] > self[j+gap]:
+                    k = self[j].get_element()
+                    self[j].set_element(self[j+gap].get_element())
+                    self[j+gap].set_element(k)
+                j += 1
+            gap -= 1
+
+        # At this point with a gap size of 1 it is insertion sort
+        self.insertion_sort()
+
+
+
+    def merge_sort(self):
+        """
+        Sort a list using merge sort
+        >>> dll = DoublyLinkedList()
+        >>> [ dll.add_first(Node(i)) for i in range(20) ]
+        >>> dll.merge_sort()
+        >>> dll
+        """
+        if self.size() < 2:
+            return
+        left = DoublyLinkedList()
+        right = DoublyLinkedList()
+        m = self.size() // 2
+        while self.size() > 0:
+            if m > 0:
+                left.add_last(self.remove(self.get_first()))
+            else:
+                right.add_last(self.remove(self.get_first()))
+            m -= 1
+
+        left.merge_sort()
+        right.merge_sort()
+        self.merge(left, right)
+
+    def merge(self, left, right):
+        while left.size() > 0 or right.size() > 0:
+            # Dump the right list if left is empty
+            if left.size() <= 0:
+                while right.size() > 0:
+                    self.add_last(right.remove(right.get_first()))
+            # Dump the left list if right is empty
+            elif right.size() <= 0:
+                while left.size() > 0:
+                    self.add_last(left.remove(left.get_first()))
+            else:
+                # Merge Nodes from each list depending on size
+                if left.get_first() < right.get_first():
+                    self.add_last(left.remove(left.get_first()))
+                else:
+                    self.add_last(right.remove(right.get_first()))
+
+    def quick_sort(self, b=None, e=None):
+        # I decided to do this one with indexing because it made it easier for
+        # me to figure out the base case for the recursion.
+        if b == None and e == None:
+            b = 0
+            e = self.size() - 1
+
+        if e <= b:
+            return
+
+        pivot = self[e]
+        i = b
+        j = i - 1
+
+        while i <= e:
+            if self[i] < pivot:
+                j += 1
+                # This prevents swapping with itself
+                if j != i:
+                    self.swap(self[j], self[i])
+            i += 1
+
+        # Put the pivot in the right place
+        j += 1
+        if self[j] != pivot:
+            # This prevents swapping with itself
+            self.swap(self[j], pivot)
+
+        self.quick_sort(b, j - 1)
+        self.quick_sort(j + 1, e)
+
+
+"""**Task 1 (25 points)**: Implement a sequential search and show the implementation works."""
+
+from numpy import random
+
+print("Testing Sequential Search")
+dL = DoublyLinkedList()
+for i in range(1,21,2):
+    dL.add_first(Node(i))
+print(dL)
+
+#The code below is broken - make it work
+node13 = dL.sequential_search(13)
+print(node13)
+
+# This is to show it works
+print("One moment please")
+import matplotlib.pyplot as plt
+from time import time
+min, max, offset = 0, 500, 20
+times = []
+dl = DoublyLinkedList()
+[ dl.add_first(Node(i+offset)) for i in range(max) ]
+for i in range(min + offset, max + offset):
+    t0 = time()
+    dl.sequential_search(i)
+    times.append(time() - t0)
+times.sort()
+plt.plot(times)
+print("As can be seen from the plot, the sequential search runs in linear time or O(n)")
+plt.show()
+print("Searching for value not in list")
+print(dl.sequential_search(0))
+
+
+
+"""**Task 2 (25 points)**: A Faster Search
+
+A **binary search** should return the node which has a value faster than the above sequential search.
+
+Implement a **binary search** and run it on the ***Doubly Linked List*** created.
+
+"""
+
+#Test your implementation here
+#The code below is broken - make it work
+print("Testing Binary Search")
+dL.quick_sort()
+node15 = dL.binary_search(15)
+print(node15)
+
+# this is to show it works
+print("One moment please")
+min, max, offset = 0, 500, 20
+times = []
+dl.quick_sort()
+for i in range(min + offset, max + offset):
+    t0 = time()
+    dl.binary_search(i)
+    times.append(time() - t0)
+times.sort()
+plt.yscale('log')
+plt.plot(times)
+print("As can be seen from the plot, the binary search runs in roughly logorithmic time or O(log n)")
+plt.show()
+print("Searching for value not in list")
+print(dl.binary_search(0))
+
+"""**Task 4 (50 points)**: Implement the two of the following sorting methods <br>
+`Bubble Sort`, `The Selection Sort`, `The Insertion Sort`, `The Shell Sort`,<br>
+`The Merge Sort`, or `The Quick Sort`
+
+If you did not like your grade on the previous ** Doubly Linked List** assignment, <br>
+I will neglect that grade and count this assignment twice if you successfully implement the `Merge Sort` or `Quick Sort` algorithm(s).
+"""
+
+#Test your implementation here
+#do a sort here
+from random import randint
+
+max = 20
+dl = DoublyLinkedList()
+[ dl.add_first(Node(i)) for i in range(max)]
+print(f"Before Quick Sort: {dl}")
+dl.quick_sort()
+print(f"After Quick Sort:  {dl}\n")
+
+dl = DoublyLinkedList()
+[ dl.add_first(Node(randint(0, max))) for i in range(max) ]
+l = dl.size()
+print(f"Before Quick Sort: {dl}")
+dl.quick_sort()
+print(f"After Quick Sort:  {dl}\n")
+
+dl = DoublyLinkedList()
+[ dl.add_last(Node(i)) for i in range(max)]
+print(f"Before Quick Sort: {dl}")
+dl.quick_sort()
+print(f"After Quick Sort:  {dl}\n")
+
+
+dl = DoublyLinkedList()
+[ dl.add_first(Node(i)) for i in range(max)]
+print(f"Before Merge Sort: {dl}")
+dl.merge_sort()
+print(f"After Merge Sort:  {dl}\n")
+
+dl = DoublyLinkedList()
+[ dl.add_first(Node(randint(0, max))) for i in range(max) ]
+l = dl.size()
+print(f"Before Merge Sort: {dl}")
+dl.merge_sort()
+print(f"After Merge Sort:  {dl}\n")
+
+dl = DoublyLinkedList()
+[ dl.add_last(Node(i)) for i in range(max)]
+print(f"Before Merge Sort: {dl}")
+dl.merge_sort()
+print(f"After Merge Sort:  {dl}\n")
diff --git a/hw4/bintest.py b/hw4/bintest.py
new file mode 100644
index 0000000..4ee9f6c
--- /dev/null
+++ b/hw4/bintest.py
@@ -0,0 +1,189 @@
+from assignment_lists_sortingandsearching_f22 import DoublyLinkedList, Node
+import matplotlib.pyplot as plt
+from time import time
+from random import randint
+
+def binstest():
+    min, max, offset = 0, 500, 20
+    times = []
+    dl = DoublyLinkedList()
+    [ dl.add_last(Node(i+offset)) for i in range(max) ]
+    print(dl)
+    for i in range(min + offset, max + offset):
+        t0 = time()
+        s = dl.binary_search(i)
+        times.append(time() - t0)
+        j = i - offset
+        print(f"{i}\t{j}\t{s}")
+    times.sort()
+    plt.yscale('log')
+    plt.plot(times)
+    plt.show()
+    print("Searching for value not in list")
+    print(dl.binary_search(0))
+
+def bstest():
+    max = 20
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(i)) for i in range(max)]
+    print(dl)
+    dl.bubble_sort()
+    print(dl, "\n")
+
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
+    l = dl.size()
+    print(dl)
+    dl.bubble_sort()
+    print(dl, "\n")
+    assert dl.size() == l
+
+    dl = DoublyLinkedList()
+    [ dl.add_last(Node(i)) for i in range(max)]
+    print(dl)
+    dl.bubble_sort()
+    print(dl)
+
+def itest():
+    max = 20
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(i)) for i in range(max)]
+    print(dl)
+    dl.insertion_sort()
+    print(dl, "\n")
+
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
+    l = dl.size()
+    print(dl)
+    dl.insertion_sort()
+    print(dl, "\n")
+    assert dl.size() == l
+
+    dl = DoublyLinkedList()
+    [ dl.add_last(Node(i)) for i in range(max)]
+    print(dl)
+    dl.insertion_sort()
+    print(dl)
+
+def stest():
+    max = 20
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(i)) for i in range(max)]
+    print(dl)
+    dl.selection_sort()
+    print(dl, "\n")
+
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
+    l = dl.size()
+    print(dl)
+    dl.selection_sort()
+    print(dl, "\n")
+    assert dl.size() == l
+
+    dl = DoublyLinkedList()
+    [ dl.add_last(Node(i)) for i in range(max)]
+    print(dl)
+    dl.selection_sort()
+    print(dl)
+
+def mtest():
+    max = 20
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(i)) for i in range(max)]
+    print(dl)
+    dl.merge_sort()
+    print(dl, "\n")
+
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
+    l = dl.size()
+    print(dl)
+    dl.merge_sort()
+    print(dl, "\n")
+    assert dl.size() == l
+
+    dl = DoublyLinkedList()
+    [ dl.add_last(Node(i)) for i in range(max)]
+    print(dl)
+    dl.merge_sort()
+    print(dl)
+
+def qtest():
+    max = 20
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(i)) for i in range(max)]
+    print(dl)
+    dl.quick_sort()
+    print(dl, "\n")
+
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
+    l = dl.size()
+    print(dl)
+    dl.quick_sort()
+    print(dl, "\n")
+    assert dl.size() == l
+
+    dl = DoublyLinkedList()
+    [ dl.add_last(Node(i)) for i in range(max)]
+    print(dl)
+    dl.quick_sort()
+    print(dl)
+
+def shtest():
+    max = 20
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(i)) for i in range(max)]
+    print(dl)
+    dl.shell_sort()
+    print(dl, "\n")
+
+    dl = DoublyLinkedList()
+    [ dl.add_first(Node(randint(0, max))) for i in range(max) ]
+    l = dl.size()
+    print(dl)
+    dl.shell_sort()
+    print(dl, "\n")
+    assert dl.size() == l
+
+    dl = DoublyLinkedList()
+    [ dl.add_last(Node(i)) for i in range(max)]
+    print(dl)
+    dl.shell_sort()
+    print(dl)
+
+def atest():
+    max = 20
+    bub = DoublyLinkedList()
+    ins = DoublyLinkedList()
+    sel = DoublyLinkedList()
+    mer = DoublyLinkedList()
+    qui = DoublyLinkedList()
+    she = DoublyLinkedList()
+
+    for _ in range(max):
+        i = randint(0, 100)
+        bub.add_last(Node(i))
+        ins.add_last(Node(i))
+        sel.add_last(Node(i))
+        mer.add_last(Node(i))
+        qui.add_last(Node(i))
+        she.add_last(Node(i))
+
+    print(f"bub {bub}\nins {ins}\nsel {sel}\nmer {mer}\nqui {qui}\nshe {she}\n")
+
+    bub.bubble_sort()
+    print(f"bub {bub}")
+    ins.insertion_sort()
+    print(f"ins {ins}")
+    sel.selection_sort()
+    print(f"sel {sel}")
+    mer.merge_sort()
+    print(f"mer {mer}")
+    qui.quick_sort()
+    print(f"qui {qui}")
+    she.shell_sort()
+    print(f"she {she}")
+