<repo_name>brandohardesty/Showcase<file_sep>/README.md
# Showcase
  This is sample code from my Data Structures course.

# DoublyLinkedList.py
  This is a sample from a lab where I was required to implement a doubly linked list with operations including insert, deletion, addition, etc.

# MixedFraction.py
  This is an object that I created for several labs. It inherits the Fraction class, not from the python standard library. I implemented class members such as numerators, denomenators, and whole numbers. The functions include rich comparison operators and overridden arithmetic operators.

# Fraction.py
  This is an object that I created for labs using MixedFraction.py. The fraction class is the parent of MixedFraction and includes similar class members like numerators and denominators. It includes rich comparison operators and overridden arithetic operators.

# cStack.py

  Here I implemented the stack data structure built on top of a list. I include functionallities such as peek, pop, and push.

# cQueue.py

  Here I implemented the queue data structure built on top of a list. I include functionalities such as enqueue and dequeue.

# binheap.py

  This is an implementation of a binary heap structure. I use this structure for building a priority queue in lab 7 to decrease the big o on ciertian operations. 

# InfixPostfix.py

  In this lab, I had to convert infix expressions to postfix expressions and then further evaluate them in another file Postfixevaluation.py

# Postfixevaluation.py

  Here I evaluate the postfix expressions created in InfixPostfix.py


# Binary and AVL Tree
  This is currently being graded and I will upload when I recieve a grade.



<file_sep>/primeFact.py
__author__ = "<NAME>"

def sieve(n = int(1e7)):
    """
    builds a list of primes less than n
    :param n: limit on our primes
    :return: reverse ordered list of primes less than n
    """
    multiples = set()
    primes = [2]
    for i in range(3,n+1,2):
        if i not in multiples:
            primes.append(i)
            multiples.update(f for f in range(i*i,n+1,i))
    return primes[::-1]

def largestPrimeFactor(n,primes):
    """
    :param n:
    :param primes: list of primes between 0 and n
    :return: the largest prime factor
    """
    for i in primes:
        if n % i == 0:
            return i
    return -1
def primeFactors(n, primes):
   factors = [largestPrimeFactor(n, primes)]
   r = n
   i = 0
   while factors[i] > 0:
     r = r // factors[i]
     i += 1
     factors.append(largestPrimeFactor(r, primes))
   factors.pop()
   product = 1
   for p in factors:
       product *= p
   if product == n:
       return factors
   else:
       factors.insert(0,n//product)
   return factors
def displayFactors(n,factors):
    out = ''
    if factors[0] > 1e14:
        out = 'Warning {:,m} is too large to guarantee all factors are prime\n'
    if factors[0] == n:
        out = '{:,d} is prime'.format(n)



def main():
   #primes = sieve()
   #dataFile = open('datfile1','r')
   #nums = []
   #nums = dataFile.readlines()
   print(largestPrimeFactor(100,sieve(9)))


   print(primeFactors(83*2,sieve(9)))


if __name__ == '__main__':
    main()

<file_sep>/Fraction.py
__author__ = '<NAME>'
from primeFact import sieve,primeFactors

class Fraction(object):

    def __init__(self, top, bottom=1):
        """ Constructor for MixedFraction.
        Initializes num and den after reducing top / bottom by their gcd.
        :param top: numerator
        :param bottom: denominator
        """
        g = self.gcd(top, bottom)
        self.num = top // g
        self.den = bottom // g

    @staticmethod
    def gcd(m, n):
        """ Euclid's Division Algorithm to find the greatest common denominator (gcd)
        of two integers.
        <http://people.uncw.edu/tompkinsj/133/proofs/quotientRemainderTheorem.htm>
        :param m: an int
        :param n: an int
        :return: the greatest common denominator of m and n
        """
        while m % n != 0:
            m, n = n, m % n
        return n

    @classmethod
    def from_string(cls,f):
        n = f[:f.index("/")]
        d = f[f.index("/") + 1:]
        return cls(int(n),int(d))



    def __str__(self):
        """ String representation of this fraction.
        :return: 'num / den'
        """
        return '{}/{}'.format(str(self.num), str(self.den))
    def __float__(self):
        result = self.num/self.den
        return result


    def __add__(self, other):
        """ Adds this fraction to the input parameter (also a Fraction or FixedFraction
        (possibly a MixedFraction). For the MixedFraction case,
        Fraction is moved to second operand so
        MixedFraction handles the addition (arithmetic promotion is required).
        :param other a Fraction, FixedFraction, or MixedFraction
        :return Fraction(n, d)
        """
        n = self.num * other.den + self.den * other.num
        d = self.den * other.den
        return Fraction(n, d)
    def __sub__(self,other):
        """ This is going to subtract another fraction from this fraction.
        :param other: The fraction subtracting this fraction
        :return: a fraction resulting from the subtraction
        """
        n = self.num * other.den - self.den * other.num
        d = self.den * other.den
        return Fraction(n,d)

    def __pow__(self, exp):
        """ Multiplies this fraction by itself exp times.
        :param exp: the exponent to be applied
        :return: Fraction(n, d) after exponentiation
        """
        n = self.num ** exp
        d = self.den ** exp
        return Fraction(n, d)
    def __truediv__(self, other):
        """
        Divides a fraction by another fraction
        :param other: another fraction
        :return: a resulting fraction from the division
        """
        n = (self.num * other.den)
        d = (self.den * other.num)
        return Fraction(n,d)
    def __sub__(self,other):
        """
        Subtracts "other" fraction from this fraction
        :param other: another fraction
        :return: a resulting fraction from the subtraction
        """
        n = (self.num * other.den) - (other.num * self.den)
        d = (self.den * other.den)
        return Fraction(n,d)
    def __mul__(self,other):
        """
        Multiplies this fraction by another fraction
        :param other: another fraction
        :return: a resulting fraction from the multiplication
        """
        n = (self.num * other.num)
        d = (self.den * other.den)
        return Fraction(n,d)
    def __eq__(self,other):
        """
        Test if two fractions are equivalent
        :param other: a fraction to test equivalency
        :return: boolean either true or false
        """
        f1 = float(self.num/self.den)
        f2 = float(other.num/other.den)

        if(f1 == f2):
            return True
        else:
            return False
    def __ne__(self,other):
        """
        Test if two fractions aren't equivalent

        :param other:a fraction to test equivalency
        :return: boolean either true or false
        """
        f1 = float(self.num / self.den)
        f2 = float(other.num / other.den)

        if (not(f1 == f2)):
            return True
        else:
            return False
    def __lt__(self,other):
        """
        Test if the current fraction is less than the other fraction
        :param other: another fraction
        :return: boolean true or false
        """
        f1 = float(self.num / self.den)
        f2 = float(other.num / other.den)

        if (f1 < f2):
            return True
        else:
            return False
    def __gt__(self,other):
        """
        Test if the current fraction is greater than the other fraction
        :param other: another fraction
        :return: boolean true or false
        """
        f1 = float(self.num / self.den)
        f2 = float(other.num / other.den)

        if (f1 > f2):
            return True
        else:
            return False
    def __ge__(self,other):
        """
        Test if the current fraction is greater than or equal to the other fraction
        :param other: another fraction
        :return: boolean true or false
        """
        f1 = float(self.num / self.den)
        f2 = float(other.num / other.den)

        if (f1 >= f2):
            return True
        else:
            return False
    def __le__(self,other):
        """
        Test if the current fraction is less than or equal to another fraction
        :param other: another fraction
        :return: boolean true or false
        """
        f1 = float(self.num / self.den)
        f2 = float(other.num / other.den)

        if (f1 <= f2):
            return True
        else:
            return False
    def __abs__(self):
        tempNum = self.num
        if(self.num < 0):
            tempNum *= -1
        else:
            pass
        return Fraction(tempNum,self.den)



    def primeFactorsOfFrac(self):
        n = sieve(max(self.num,self.den))
        factOfNum = primeFactors(self.num,n)
        factOfDen = primeFactors(self.den,n)
        return (factOfNum,factOfDen)




<file_sep>/cQueue.py
import DoublyLinkedList
__author__ = "<NAME>"

class Queue:

    def __init__(self):
        """
        Creates a new Queue
        """
        self.queue = DoublyLinkedList.DoublyLinkedList()
    def is_empty(self):
        """
        Test if the Queue is empty
        :return: True or False
        """
        return self.queue.size == 0
    def size(self):
        """
        Gives the size of the Queue
        :return: the number of elements in the queue
        """
        return self.queue.size
    def enqueue(self,value):
        """
        Adds a node object to the front of the queue
        :param value: The value
        :return: nothing
        """
        self.queue.addFront(value)
    def dequeue(self):
        """
        Remove the last object in the queue
        :return: The last value in the queue
        """
        return self.queue.removeRear()



<file_sep>/cStack.py
import DoublyLinkedList
__author__ = "<NAME>"

class Stack:

    def __init__(self):
        """
        Creates a new stack
        """
        self.stack = DoublyLinkedList.DoublyLinkedList()

    def isEmpty(self):
        """
        Test if the stack is empty
        :return: True or false
        """
        return self.stack.size == 0

    def size(self):
        """
        Gives the size of the stack
        :return: The number of elements in the stack
        """
        return self.stack.size
    def push(self,value):
        """
        Adds a node to the rear of the stack
        :param value: The object you want to add
        :return: nothing
        """
        self.stack.addRear(value)
    def pop(self):
        """
        Removes the last item on the stack
        :return: the value of the last item
        """
        if self.isEmpty():
            raise Exception
        return self.stack.removeRear()
    def peek(self):
        """
        Looks at the last item on the stack
        :return: the value of the last item on the stack
        """

        return self.stack.atIndex(self.stack.size-1)


<file_sep>/InfixPostfix.py
__author__ = "<NAME>"
import cStack
import DoublyLinkedList
import MixedFraction



def infixToPostfix(infixexpr):
    prec = {}
    prec["^"] = 4
    prec["*"] = 3
    prec["/"] = 3
    prec["+"] = 2
    prec["-"] = 2
    prec["("] = 1
    opStack = cStack.Stack()
    postfixList = []
    tokenList = infixexpr.split(" ")

    for token in tokenList:
        if token.isnumeric() or token.isalpha() or token.count(".") == 1 or (token.count("/") == 1 and len(token) > 1):
            postfixList.append(token)
        elif token == '(':
            opStack.push(token)
        elif token == ')':
            topToken = opStack.pop()
            while topToken != '(':
                try:
                    postfixList.append(topToken)
                    topToken = opStack.pop()
                except Exception:
                    print("Bad expession: {}".format(infixexpr))
                    break
        else:
            try:
                while (not opStack.isEmpty()) and \
               (prec[opStack.peek()] >= prec[token]):
                  postfixList.append(opStack.pop())
            except KeyError:
                print("Key Error: {}".format(infixexpr))
                break
            opStack.push(token)

    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    return " ".join(postfixList)


def main():
    print(infixToPostfix("A * B + C ^ D"))
    print(infixToPostfix("( 4.4 + 4.6 ) ^ ( 2 / ( 1 + 3 ) )"))
    print(infixToPostfix("( 2 ^ 20 ) ^ ( 2 / ( 1 + 3 ) )"))
    print(infixToPostfix("A * B ) + ( C ^ D )"))
    print(infixToPostfix("( A * B ) + (C ^ D )"))
    print(infixToPostfix("7 + 9 * 8 / 4 ^ 2"))
    print(infixToPostfix("( 17 + 9 ) * 3 / ( 5 - 3 ) ^ 4"))
if __name__ == "__main__":
    main()




<file_sep>/lab7.py
__author__ = '<NAME>, <NAME> modified by <NAME> and student'

import MixedFraction
import random
import math
import binheap
import csv
import time
class Node:
    def __init__(self, initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, newdata):
        self.data = newdata

    def setNext(self, newnext):
        self.next = newnext


class Queue23:
    def __init__(self):
        self.head = None

    def search(self, item):
        current = self.head
        found = False
        stop = False
        while current is not None and not found and not stop:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()
        return found

    def add(self, item):
        current = self.head
        previous = None
        stop = False
        while current is not None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()

        temp = Node(item)
        if previous is None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)

    def isEmpty(self):
        """ Returns True if the priority queue is empty, False otherwise."""
        return self.head is None

    def size(self):
        """ Returns the current size of the priority queue."""
        current = self.head
        count = 0
        while current is not None:
            count = count + 1
            current = current.getNext()
        return count

    def insert(self, k):
        self.add(k)

    def findMin(self):
        """ Finds and returns the minimum value in the priority queue.
        :return: the object with the minimum value
        """
        return self.head.getData()

    def delMin(self):
        """ Removes and returns the minimum value in the priority queue. Catches the potential
        IndexError.
        :return: minimum value in the priority queue, None if attempted on an empty heap
        """
        retval = None
        try:
            retval = self.head.getData()
            self.head = self.head.next


        except IndexError:
            return None

        return retval

    def buildPriorityQueue(self, alist):
        """ Builds an otherwise empty priority queue from the list parameter.
        :param alist: A list of comparable objects.
        :return: None
        """

        blist = list(alist)
        blist.sort()
        pNode = Node(blist[0])
        self.head = pNode
        del blist[0]
        for i in range(len(blist)):
            t = Node(blist[0])
            pNode.next = t
            pNode = t
            del blist[0]










class Queue12:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        """ Returns True if the priority queue is empty, False otherwise."""
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        """ Returns the current size of the priority queue."""
        return len(self.items)

    def insert(self, k):
        """
        inserts k into the priority queue so the priority is maintained
        :param k:
        :return: None
        """
        self.items.append(k)
        self.items.sort()

    def findMin(self):
        """ Finds and returns the minimum value in the priority queue.
        :return: the object with the minimum value
        """
        return self.items[0]

    def delMin(self):
        """ Removes and returns the minimum value in the priority queue. Catches the potential
        IndexError.
        :return: minimum value in the priority queue, None if attempted on an empty heap
        """
        retval = None
        try:
            retval = self.items[0]
            del self.items[0]
        except IndexError:
            return None
        return retval

    def buildPriorityQueue(self, alist):
        """ Builds an otherwise empty priority queue from the list parameter.
        :param alist: A list of comparable objects.
        :return: None
        """
        self.items = alist
        self.items.sort()
def generateDataSet():
    randomMixedFractions = list()
    for i in range(40000):
        randomMixedFractions.append(MixedFraction.MixedFraction(random.randint(1,100),random.randint(1,100)))

    dataSets = {"10k":[],"20k":[],"30k":[],"40k":[]}
    dataSets["10k"] = randomMixedFractions[:10000]
    dataSets["20k"] = randomMixedFractions[:20000]
    dataSets["30k"] = randomMixedFractions[:30000]
    dataSets["40k"] = randomMixedFractions[:40000]

    return dataSets
def getData(dataList):
    minimum = min(dataList)
    maximum = max(dataList)
    totalListVal = MixedFraction.MixedFraction(0,1)
    for i in dataList:
        totalListVal += i
    avg = totalListVal/MixedFraction.MixedFraction(len(dataList),1)
    delta = MixedFraction.MixedFraction(0,1)
    deltaList = list()
    realAvg = 0
    for i in range(len(dataList)):
        delta = dataList[i] - avg
        if(delta == MixedFraction.MixedFraction(0,1)):
            realAvg = dataList[i]
            deltaList.append(abs(delta))
        else:
            deltaList.append(abs(delta))
    realAvg = dataList[deltaList.index(min(deltaList))]

    return (minimum,maximum,realAvg)

    

def timeOperations(data):



    listQ = Queue12()
    linkedQ = Queue23()
    binQ = binheap.BinHeap()
    keys = ["10k","20k","30k","40k"]

    with open("table.csv", "w") as file:
        nList = [10000, 20000, 30000, 40000]
        writer = csv.writer(file)
        writer.writerow(["listQ", "linkedQ", "binQ"])
        for i in keys:
            listQ.buildPriorityQueue(data[i])
            linkedQ.buildPriorityQueue(data[i])
            binQ.buildPriorityQueue(data[i])





            st = time.clock()
            listQ.findMin()
            sp = time.clock()
            listQT = sp - st


            st = time.clock()
            linkedQ.findMin()
            sp = time.clock()
            linkedQT = sp - st


            st = time.clock()
            binQ.findMin()
            sp = time.clock()
            binQT = sp - st

            writer.writerow([listQT,linkedQT,binQT])

    with open("insert.csv", "w") as file:
        nList = [10000, 20000, 30000, 40000]
        insertWriter = csv.writer(file)
        insertWriter.writerow(["listQ", "linkedQ", "binQ"])
        for i in keys:
            listQ.buildPriorityQueue(data[i])
            linkedQ.buildPriorityQueue(data[i])
            binQ.buildPriorityQueue(data[i])
            avgE = getData(data[i])[2]

            st = time.clock()
            listQ.insert(avgE)
            sp = time.clock()
            listQT = sp - st


            st = time.clock()
            linkedQ.insert(avgE)
            sp = time.clock()
            linkedQT = sp - st


            st = time.clock()
            binQ.insert(avgE)
            sp = time.clock()
            binQT = sp - st
            insertWriter.writerow([listQT,linkedQT,binQT])



    with open("del.csv", "w") as file:
        nList = [10000, 20000, 30000, 40000]
        delWriter = csv.writer(file)
        delWriter.writerow(["listQ", "linkedQ", "binQ"])
        for i in keys:
            listQ.buildPriorityQueue(data[i])
            linkedQ.buildPriorityQueue(data[i])
            binQ.buildPriorityQueue(data[i])

            st = time.clock()
            listQ.delMin()
            sp = time.clock()
            listQT = sp - st

            st = time.clock()
            linkedQ.delMin()
            sp = time.clock()
            linkedQT = sp - st

            st = time.clock()
            binQ.delMin()
            sp = time.clock()
            binQT = sp - st

            delWriter.writerow([listQT,linkedQT,binQT])






















    #finding minimum test 10k through 40k




def main():
    timeOperations(generateDataSet())
    



    pass


if __name__ == '__main__':
    main()
<file_sep>/MixedFraction.py
from Fraction import Fraction
__author__ = '<NAME>'


class MixedFraction (Fraction):

    def __init__(self, top, bottom=1):
        """ Initializes num and den after reducing top / bottom
        by their gcd by invoking super.
        
        Adds fields whole and n, initialized to 0.
        If num > den, assigns the quotient to whole and the remainder to n.
        :param top: numerator
        :param bottom: denominator
        """
        super().__init__(top, bottom)
        self.whole = 0
        self.n = 0
        if self.num >= self.den:
            self.whole = self.num // self.den
            self.n = self.num % self.den

    def __str__(self):
        """ String representation of this fraction.

        Empty strings are used in place of 0.
        :return: whole num / den :: num / den :: whole
        """
        if self.whole == 0:
            return super().__str__()
        elif self.n == 0:
            return str(self.whole)
        return '{} {}/{}'.format(str(self.whole), str(self.n), str(self.den))

    def __add__(self, other):
        """ Adds this fraction to the input parameter (also a
        Fraction (possibly a MixedFraction).
        
        :param other Fraction or MixedFraction
        :return MixedFraction(n, d)
        """
        n = self.num * other.den + self.den * other.num
        d = self.den * other.den
        return MixedFraction(n, d)

    def __sub__(self, other):
        """ Subtracts the input parameter (also a
        Fraction (possibly a MixedFraction) from this fraction.
        
        :param other Fraction or MixedFraction
        :return MixedFraction(n, d)
        """


        n = (self.num * other.den) - (self.den * other.num)
        d = self.den * other.den




        return MixedFraction(n,d)
    def __mul__(self,other):
        """
        Multiplies a mixed fraction by another mixed fraction or fraction
        :param other: another fraction or mixed fraction
        :return: the resulting mixed fraction from the multiplication
        """

        n = (self.num) * (other.num)
        d = (self.den * other.den)


        return MixedFraction(n,d)
    def __truediv__(self,other):
        """
        Divides a mixed fraction by another mixed fraction or a fraction
        :param other: another fraction or mixed fraction
        :return: the resulting mixed fraction from the division
        """

        n = (self.num) * other.den
        d = (self.den * other.num)

        return MixedFraction(n,d)




    def __pow__(self, exp):
        """ Multiplies this fraction by itself exp times.

        :param exp: the exponent to be applied
        :return: MixedFraction(n, d) after exponentiation
        """
        f = super().__pow__(exp)
        return MixedFraction(f.num, f.den)


    @classmethod
    def from_string(cls,f):
        if (f.count(" ") == 1):
            w = f[:f.index(" ")]
            n = f[f.index(" ") + 1:f.index("/")]
            d = f[f.index("/")+1:]
            return cls(int(w) * int(d) + int(n), int(d))
        if(f.count(" ") == 0):
            n = f[:f.index("/")]
            d = f[f.index("/") + 1:]
            return cls(int(n),int(d))


    
<file_sep>/lab6_quicksorts.py
import os
import sys
from urllib.request import urlopen
import matplotlib.pyplot as plt
from time import clock
import math
import random
__author__ = '<NAME>'

def plot(data_map, title, xlabel='N', ylabel='time - seconds'):
    """
    Plots the two sets of data (minimum 8 datapoints) in the dictionary data_map using its keys as labels
    :param data_map: a dictionary containing the x data points and two sets of y data points
    :param title: Map heading
    :param xlabel: abscissa axis
    :param ylabel: ordinate axis
    :return: None
    """
    labels = list(data_map.keys())
    plt.title(title)
    x = data_map[labels[0]]
    y1 = data_map[labels[1]]
    y2 =  data_map[labels[2]]
    plt.plot(x, y1, label=labels[1], color='g')
    plt.plot(x,y2, label=labels[2], color='b')

    plt.xlabel(xlabel)
    plt.ylabel(ylabel)

    plt.text(x[2], y1[2], 'f({0:,}) = {1:.2}\nn = {0:,}'.format(x[2], y1[2]), color='g')  # n, f(n)
    plt.text(x[5], y1[5], 'f({:,}) = {:.2}\n= {:.2}f(n) '.format(x[5], y1[5], y1[5]/y1[2]), color='g')  # n, f(2n)/f(n)

    plt.text(x[0], y2[0], 'f({0:,}) = {1:.2}\nn = {0:,}'.format(x[0], y2[0]), color='b')  # n, f(n)
    plt.text(x[7], y2[7], 'f({:,}) = {:.2}\n= {:.2}f(n) '.format(x[7], y2[7], y2[7] / y2[0]), color='b')  # n, f(8n)/f(n)

    plt.legend()
    plt.show()

def get_from_web(web_addr, save=True):
    """
    Retrieves and saves the resource located at the provided URL
    :param web_addr: URL
    :param save: default Boolean saves to a file in a directory named data
    :return: a list of strs created from space delimited str tokens in the web resource
    """
    response = urlopen(web_addr).read()  # urlopen creates the connection
                                         # read returns a bytes object
    file_name = web_addr[web_addr.rfind('/') + 1:]
    if not os.path.exists('data'):
        os.makedirs('data')
    if save:
        with open('data/' + file_name, 'wb') as f:
            f.write(response)
    
    return response.decode().split()

def quicksort(xlist):
    qsort(xlist, 0, len(xlist)-1)
    
def qsort(xlist, L, R):
    i = L
    j = R
    ip = L + (R - L) // 2  # index of middle element
    p = xlist[ip] # pivot element in the middle
         
    while i <= j:
        while xlist[i] < p: i += 1
        while xlist[j] > p: j -= 1
        if i <= j: # swap and increment i, decrement j
            xlist[i], xlist[j] = xlist[j], xlist[i]
            i += 1
            j -= 1
			
    if L < j:  # sort left list
        qsort(xlist, L, j)
    if i < R:  # sort right list
        qsort(xlist, i, R)

def bquickSort(alist):
   bquickSortHelper(alist,0,len(alist)-1)

def bquickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition2(alist,first,last)

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


def partition2(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 genData():
    file = open('data.txt','w')

    set1 = [-1*(i**2) for i in range(-50,51)]
    set2 = [i for i in range(50,0-1)]

    for x in range(0,51):
        set2.append(x)


    file.write('Data Set 1\n')
    for x in range(len(set1)):
        file.write(str(set1[x])+'\n')

    file.write('Data Set 2\n')
    for x in range(len(set2)):
        file.write(str(set2[x])+'\n')


    return (set1,set2)

def main(start, data, func, title):
    data_sorted = sorted(data, reverse=True)   
    data_map = {'x':[], 'randomized data':[], 'sorted data':[]}
    print('\n{}'.format(title))
    temp = 0
    temp2 = 0
    step = start
    end = start + 8*step + 1
    for n in range(start, end, step):
        ulist = data[:n]
        slist = data_sorted[:n]
        expected = temp * (n ** 2)
        expected2 = temp2 * (n * math.log10(n))
        
        start1 = clock()
        func(ulist)
        time1 = clock() - start1
        temp2 = time1 / (n * math.log10(n))
        start2 = clock()
        func(slist)
        time2 = clock() - start2
        temp = time2 / (n**2)


        data_map['x'].append(n)
        data_map['randomized data'].append(time1)
        data_map['sorted data'].append(time2)

    x = data_map['x']
    y1 = data_map['randomized data']
    y2 = data_map['sorted data']
    analyze_data(x, y1, 'green')
    analyze_data(x, y2, 'blue')
        
    plot(data_map, title)



def analyze_data(x, y, color='green'):
    if color is 'blue':
        print('Sorted {}'.format(color))
    else:
        print('Unsorted {}'.format(color))
    print('f({0:,}) = {1:.2}, n = {0:,}'.format(x[2], y[2]))
    print('f({:,}) = {:.2}, = {:.2}f(n) '.format(x[5], y[5], y[5] / y[2]))
    print('f({0:,}) = {1:.2}, n = {0:,}'.format(x[0], y[0]))
    print('f({:,}) = {:.2}, = {:.2}f(n) '.format(x[7], y[7], y[7] / y[0]))
    if y[5]/y[2] < 1.5 or y[7]/y[0] < 6 :  # output ratio for doubled input less than double
        print('The {} graph is better than linear? \n \
              Expected: f(2n) ≅ 2*f(n), f(8n) ≅ 8*f(n)'.format(color))
    elif round(y[5]/y[2]) == 2 or round(y[7]/y[0]) == 8:  # output ratio for doubled input is also double
        print('The {} graph appears to be linear. \n \
              Expected: f(2n) ≅ 2*f(n), f(8n) ≅ 8*f(n)'.format(color))
    elif round(y[5]/y[2])  >= 3 and round(y[7]/y[0]) > 32:
        # output ratio for double input is quadratic, for 8*input it is 64f(n)
        print('****The {} graph may be quadratic. \n \
              Expected: f(2n) ≅ 4*f(n), f(8n) ≅ 64*f(n) ****\n'.format(color))
    elif round(y[5]/y[2])  >= 4 or round(y[7]/y[0])  >= 64:
        # output ratio for doubled input is quadratic, for 8 * input it is 64f(n)
        print('**************The {} graph appears to be quadratic. \n \
              Expected: f(2n) ≅ 4*f(n), f(8n) ≅ 64*f(n) **************\n'.format(color))


def conclusions():
    ans1 = """ The list is being partitioned the maximum amount of times if you pivot on the endpoints of the dataset. The reason the sort runs the maximum amount of times is because the list only gets smaller by one each run. """
    print('\nDiscussion regarding the dataset size limitations exhibited using "quickSort - first element pivot" in Step 1.\n\t{}'.format(ans1))
    ans2 = """ Actual (6.2e-05)/30^2 = (expected time)/60^2" Expected Time calculation = 2.48e-4 and the actual time was 2.2e-4 so the calculations are accurate."""
    print('Calculations for Step 2 showing actual vs expected performance of "quicksort - middle pivot"\n\t{}'.format(ans2))
    ans3 = """ I generated a data set where the data increased until the middle was the maximum value. The decreased from the middle value to the end of the data set. This allows for decreasing the list size by 1 each run."""
    print('Design particulars for your datasets created in Step 2.\n\t{}'.format(ans3))
    ans4 = """ Yes, my generated data set degrades the run time to n^2 because it results in the maximum number of runs."""
    print('Does the middle pivot solve the quicksort degradation problem?\n\t{}'.format(ans4))


if __name__ == '__main__':    
    data = get_from_web('http://people.uncw.edu/tompkinsj/231/resources/dictionary.txt')
    print("""This Lab test various quicksort algorithms using particular datasets to show graphically that the 
    algorithm may degrade to O(n**2) given the right conditions.""")
    print("""In the second part, we attempt to degrade quicksort with middle pivot using different combinations of  
    datasets since it efficiently handled presorted data sets.""")
    print("Initial dataset: type {}, type element {}, first element {}, last element {}, size {:,}.".
          format(type(data), type(data[0]), data[0], data[-1], len(data)))
    main(50, data, bquickSort, 'Unsorted vs Sorted Quick Sorts - middle pivot')
    start_size = 50  # invoke main with a start_size appropriate for the recursive first pivot quickSort, same data, new function name, and new title
    main(start_size,data, quicksort, 'Unsorted vs Sorted Quick Sorts - first element pivot')
    
    # populate data with the return value from your dataset building function which builds and saves dataset to data folder
    title = ' '  # invoke main with a modified title
    datatup = genData()
    main(10,datatup[0], bquickSort, 'Unsorted {} vs Sorted {} - middle pivot'.format(title,title))
    conclusions()
    
<file_sep>/DoublyLinkedList.py
__author__ = "<NAME>"


class DoublyLinkedNode:
    """ A single node in a doubly-linked list.
        Contains 3 instance variables:
            data: The value stored at the node.
            prev: A pointer to the previous node in the linked list.
            next: A pointer to the next node in the linked list.
    """

    def __init__(self, value):
        """
        Initializes a node by setting its data to value and
        prev and next to None.
        :return: The reference for self.
        """
        self.data = value
        self.prev = None
        self.next = None


class DoublyLinkedList:
    """
    The doubly-linked list class has 3 instance variables:
        head: The first node in the list.
        tail: The last node in the list.
        size: How many nodes are in the list.
    """

    def __init__(self):
        """
        The constructor sets head and tail to None and the size to zero.
        :return: The reference for self.
        """
        self.head = None
        self.tail = None
        self.size = 0

    def addFront(self, value):
        """
        Creates a new node (with data = value) and puts it in the
        front of the list.
        :return: None
        """
        newNode = DoublyLinkedNode(value)
        if (self.size == 0):
            self.head = newNode
            self.tail = newNode
            self.size = 1
        else:
            newNode.next = self.head
            self.head.prev = newNode
            self.head = newNode
            self.size += 1

    def addRear(self, value):
        """
        Creates a new node (with data = value) and puts it in the
        rear of the list.
        :return: None
        """
        newNode = DoublyLinkedNode(value)
        if (self.size == 0):
            self.head = newNode
            self.tail = newNode
            self.size = 1
        else:
            newNode.prev = self.tail
            self.tail.next = newNode
            self.tail = newNode
            self.size += 1

    def removeFront(self):
        """
        Removes the node in the front of the list.
        :return: The data in the deleted node.
        """
        value = self.head.data
        self.head = self.head.next
        if self.head != None:
            self.head.prev = None
        self.size -= 1
        return value

    def removeRear(self):
        """
        Removes the node in the rear of the list.
        :return: The data in the deleted node.
        """
        value = self.tail.data
        self.tail = self.tail.prev
        if self.tail != None:
            self.tail.next = None
        self.size -= 1
        return value

    def printItOut(self):
        """
        Prints out the list from head to tail all on one line.
        :return: None
        """
        temp = self.head
        while temp != None:
            print(temp.data, end=" ")
            temp = temp.next
        print()

    def printInReverse(self):
        """
        Prints out the list from tail to head all on one line.
        :return: None
        """
        temp = self.tail
        while temp != None:
            print(temp.data, end=" ")
            temp = temp.prev
        print()


    def atIndex(self, index):
        """
        Retrieves the data of the item at index.
        :param index: The index of the item to retrieve.
        :return: Returns the data of the item.
        """
        count = 0
        temp = self.head
        while count < index:
            count += 1
            temp = temp.next
        if not temp:
            return None
        return temp.data
    def indexOf(self,value):
        for i in range(self.size):
            if (value == self.atIndex(i)):
                return i
        return -1
    def insertAt(self,index,value):
        newNode = DoublyLinkedNode(value)
        temp = self.head

        for i in range(index):
            temp = temp.next

        if(index == 0):
            self.addFront(value)
        elif(index == (self.size)):
            self.addRear(value)
        else:
            temp.prev.next = newNode
            newNode.prev = temp.prev
            temp.prev = newNode
            newNode.next = temp
        self.size += 1
    def removeAt(self,index):
        temp = self.head

        for i in range(index):
            temp = temp.next

        if(index == 0):
            return self.removeFront()

        elif(index == (self.size-1)):
            return self.removeRear()
        else:
            print(self.size)
            value = temp.data
            temp.prev.next = temp.next
            temp.next.prev = temp.prev
        self.size -= 1
        return value
















def main():
    dll = DoublyLinkedList() 
    dll.addRear(5) 
    dll.addRear(2) 
    dll.addRear(25) 
    dll.addRear(-4)
    dll.insertAt(2,7) 
    dll.printItOut()

    x = dll.removeAt(2)
    dll.printItOut()
    print("\tThe item removed was {}.".format(x))
    x = dll.removeAt(0)
    dll.printItOut()
    print("\tThe item removed was {}.".format(x))
    x = dll.removeAt(2)
    dll.printItOut()
    print("\tThe item removed was {}.".format(x))

    # optionally
    print()
    dll = DoublyLinkedList() 
    dll.addRear(1) 
    dll.addRear(2) 
    dll.addRear(4) 
    dll.addRear(25) 
    dll.addRear(35) 
    dll.printItOut()
    for i in range(dll.size):
        y = dll.atIndex(i)
        yIndex = dll.indexOf(y)
        print('The value at index {:d} is {} for which indexOf({}) returned {}.'.format(i,y,y,yIndex))
    print('indexOf(-10) is {}'.format(dll.indexOf(-10)))
    print('The dll size is {}.'.format(dll.size))


if __name__ == '__main__':
    main()
<file_sep>/Postfixevaluation.py
__author__ = "<NAME>"
from InfixPostfix import  infixToPostfix
import DoublyLinkedList
import cStack
import MixedFraction

postfixExpressions = ['4.4 4.6 + 2 1 3 + / ^', '2 20 ^ 2 1 3 + / ^', '2 20 + 2 1 3 + + *', '2 -1 3 + -']
infixExpressions = ["7 + 9 * 8 - 4 ^ 2", "7 + 9 * 8 / 4 ^ 2", "( 17 + 9 ) * 3 / ( 5 - 3 ) ^ 4", "7.5 + 9 - 1.8 / 4 ^ 2.5"]
def evaluatePost(exp):
    stack = cStack.Stack()
    tokenList = exp.split(" ")
    for i in tokenList:
        try:
            if(i.count("/") == 1 and len(i) > 1):
                stack.push(float(MixedFraction.MixedFraction.from_string(i)))
            else:
                i = float(i)
                stack.push(i)
        except:
            if (i in "*/+-^"):
                b = stack.pop()
                a = stack.pop()
                if (i == "*"):
                    stack.push(a * b)
                elif (i == "/"):
                    stack.push(a / b)

                elif (i == "+"):
                    stack.push(a + b)
                elif (i == "-"):
                    stack.push(a - b)
                elif (i == "^"):
                    stack.push(a ** b)



    return stack.peek()

def main():
    for i in postfixExpressions:
        result = evaluatePost(i)
        out = "{} = {}".format(i,result)
        print(out)
    for i in infixExpressions:
        c = infixToPostfix(i)
        result = evaluatePost(c)
        out = "{} = {}".format(i, result)
        print(out)
if __name__ == "__main__":
    main()






<file_sep>/binheap.py
__author__ = '<NAME>, <NAME> modified by <NAME>'

class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    def insert(self, k):
        """
        inserts k into the priority queue so the priority is maintained
        :param k:
        :return: None
        """
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def findMin(self):
        """ Finds and returns the minimum value in the priority queue.
        :return: the object with the minimum value
        """
        return self.heapList[1]
          
    def delMin(self):
        """ Removes and returns the minimum value in the priority queue. Catches the potential
        IndexError.
        :return: minimum value in the priority queue, None if attempted on an empty heap
        """
        retval = None
        try:
          retval = self.heapList[1]
          self.heapList[1] = self.heapList[self.currentSize]
          self.currentSize = self.currentSize - 1
          self.heapList.pop()
          self.percDown(1)
        except IndexError:
            pass
        return retval
    
    def isEmpty(self):
        """ Returns True if the priority queue is empty, False otherwise."""
        return self.currentSize == 0

    def size(self):
        """ Returns the current size of the priority queue."""
        return self.currentSize

    def buildPriorityQueue(self, alist):
        """ Builds an otherwise empty priority queue from the list parameter.
        :param alist: A list of comparable objects.
        :return: None
        """
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]
        while (i > 0):
          self.percDown(i)
          i = i - 1

    def percUp(self, i):
        """ Percolates an item, at index i, as far up in the tree as it needs to go to maintain the heap property
        :param i: the index of the item
        :return: None
        """
        while i // 2 > 0:
          if self.heapList[i] < self.heapList[i // 2]:
             tmp = self.heapList[i // 2]
             self.heapList[i // 2] = self.heapList[i]
             self.heapList[i] = tmp
          i = i // 2
  
    def percDown(self,i):
        """ Invoked by delMin and buildPriorityQueue. Invokes minChild.
        Since the heap property requires that the root of the tree be the smallest item in the tree,
        finding the minimum item is easy.
        The hard part of delMin is restoring full compliance with
        the heap structure and heap order properties after the root has been removed.
        We can restore our heap in two steps.
        First, we will restore the root item by taking the last item in the list and moving it to the root position.
        Moving the last item maintains our heap structure property.
        However, we have probably destroyed the heap order property of our binary heap.
        Second, we will restore the heap order property by pushing the new root node down the tree to its proper position.
        :param i:
        :return: None
        """
        while (i * 2) <= self.currentSize:
          mc = self.minChild(i)
          if self.heapList[i] > self.heapList[mc]:
              tmp = self.heapList[i]
              self.heapList[i] = self.heapList[mc]
              self.heapList[mc] = tmp
          i = mc

    def minChild(self,i):
        """ Invoked by percDown. If there is only one child, its index is returned.
        If there are two children, then the smaller childs index is returned.
        :param i: index of the parent
        :return: the index of the minimum child
        """
        if i * 2 + 1 > self.currentSize:
          return i * 2
        else:
          if self.heapList[i*2] < self.heapList[i*2+1]:
              return i * 2
          else:
              return i * 2 + 1

def main():
    print('Invoking BinHeap()')
    bh = BinHeap()
    print('Size: {}, isEmpty(): {}, delMin(): {}'.format(bh.size(), bh.isEmpty(), bh.delMin()))
    data = [9,5,6,2,3]
    print('Invoking buildPriorityQueue({}) which invokes percDown from the middle of the list to the top.'.format(data))
    bh.buildPriorityQueue(data)
    x = -5
    print('Invoking insert({0}) which appends {0} to the heap then invokes percUp.'.format(x))
    bh.insert(x)
    print('Size: {}, isEmpty(): {}'.format(bh.size(), bh.isEmpty()))
    print('''while bh.size() > 0: invoking delMin(),
which stores the min value for later return,
places the last element first, reduces the size, pops the end
then invokes percDown''')
    while bh.size() > 0:
        print(bh.delMin())

if __name__ == '__main__':
    main()
