1 files changed, 189 insertions, 0 deletions
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}")
+