ASK Huiswerkopdracht 4

insertion_sort.py

def insertion_sort(lst):
    """
    Implementatie met twee while loops, omdat recursief alleen maar moeite is.
    Pseudocode is 1:1 overgenomen zonder erbij na te denken (niet nagedacht over var names, `for i in range()` ipv `while`, etc)
    """
    i = 1
    while i < len(lst):
        x = lst[i]
        j = i - 1
        while j >= 0 and lst[j] > x:
            lst[j + 1] = lst[j]
            j = j - 1
        lst[j + 1] = x
        i = i + 1


def array_is_same(a, b) -> bool:
    """Hier is vast een built-in functie voor, maar ik kon hem niet vinden"""
    if len(a) != len(b):
        return False

    for i in range(len(a)):
        if a[i] != b[i]:
            return False
    
    return True


if __name__ == "__main__":
    # Deterministic dataset, aka no random data
    test_sets = [
        # input data, expected output data
        [[5,4,3,2,1], [1,2,3,4,5]],
        [[420, 69, 12], [12, 69, 420]],
        [["jullie", "hebben", "allemaal", "een", "onvoldoende"], ["allemaal", "een", "hebben", "jullie", "onvoldoende"]], # Strings (looks at first character, aka a simple A-Z sort)
        [[6, 7, 88, 120], [6, 7, 88, 120]], # Already sorted list
    ]

    print("Testing insertion_sort")

    # Run test for each dataset
    for i, test in enumerate(test_sets):
        print("Test " + str(i) + ": ", end='')
        insertion_sort(test[0])

        if array_is_same(test[0], test[1]):
            print("Passed")
        else:
            print("Failed")

search_algorithm.py

def linear_search(arr, to_find, i = 0):
    """Returns object index, or -1 if not found"""
    if i >= len(arr):
        return -1
    elif arr[i] == to_find:
        return i
    else:
        return linear_search(arr, to_find, i + 1)


def binary_search(arr, to_find, l, r):
    """
    Returns object index, or -1 if not found

    arr = **sorted** array
    l = start index
    r = end index
    """
    if l > r:
        return -1
    
    mid = l + (r - l) // 2

    if arr[mid] == to_find:
        return mid
    elif arr[mid] > to_find:
        # Object is in left side of the array
        return binary_search(arr, to_find, l, mid - 1)
    else:
        # Object is in right side of the array
        return binary_search(arr, to_find, mid + 1, r)


if __name__ == "__main__":
    # Deterministic dataset, aka no random data
    test_sets = [
        # array, object to find, object can be found
        [[1, 2, 3, 4, 5], 4, True],
        [["icor", "is", "niet leuk"], "leuk", False],
        [["het", "is", "koud", "buiten"], "koud", True],
        [[6, 5, 4, 7, 8, 9, 10, 30, 40, 50], 11, False],
        [[6, 5, 4, 7, 8, 9, 10, 30, 40, 50], 10, True],
        [[6, 5, 4, 7, 8, 9, 10, 30, 40, 50, 1], 10, True],
    ]

    print("Testing linear_search")

    # Run test for each dataset
    for i, test in enumerate(test_sets):
        print("Test " + str(i) + ": ", end="")
        idx = linear_search(test[0], test[1])

        if (idx != -1 and test[0][idx] == test[1]) == test[2]:
            print("Passed")
        else:
            print("Failed")

    print("\nTesting binary_search")

    # Run test for each dataset
    for i, test in enumerate(test_sets):
        print("Test " + str(i) + ": ", end="")

        # Binary search only works on sorted arrays
        sorted_input = test[0].copy()
        sorted_input.sort()

        idx = binary_search(sorted_input, test[1], 0, len(sorted_input) - 1)

        if (idx != -1 and sorted_input[idx] == test[1]) == test[2]:
            print("Passed")
        else:
            print("Failed")

    # Bonus RecursionError
    # import sys
    # print("\nBonus: RecursionError")
    # py_stack_limit = sys.getrecursionlimit() # Usually 1000
    # arr = [0] * py_stack_limit
    # linear_search(arr, "boom")

text.md

Sorteeralgoritme

Pseudocode

Implementatie 1: Insertion sort

i ← 1
while i < length(A)
    x ← A[i]
    j ← i - 1
    while j >= 0 and A[j] > x
        A[j+1] ← A[j]
        j ← j - 1
    end while
    A[j+1] ← x[4]
    i ← i + 1
end while

Implementatie 2: Recursieve insertion sort

function insertionSortR(array A, int n)
     if n>0
        insertionSortR(A,n-1)
        x ← A[n]
        j ← n-1
        while j >= 0 and A[j] > x
            A[j+1] ← A[j]
            j ← j-1
        end while
        A[j+1] ← x
     end if
 end function

De eerste implementatie maakt gebruik van twee loops waar de tweede implementatie gebruik maakt van slechts een loop en het roept zichzelf aan (recursief).

Bron: https://en.wikipedia.org/wiki/Insertion_sort

Best en worst case

Best case is een al gesorteerde lijst want dan moet hij alleen voor elk element kijken of hij op de goede plek staat. O(n)

Worst case is als de lijst precies verkeerd om staat. O(n^2)

Voorbeeld (als ik het goed begrijp): Lijst heeft 10 elementen. Best case: 10 Worst case: 100