<jupyter_start><jupyter_text><NAME> BMI 203, Winter 2020 Homework 1  Generating 100 random vectors of different sizes<jupyter_code>import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt<jupyter_output><empty_output><jupyter_text>The cell below is a helper function to help me find the necessary time complexity for my bubble and insertion sorting algorithms.<jupyter_code>vector_size = np.array([100, 200, 300, 400, 500, 600, 700, 800, 900, 1000])

def t_complexity(sorting_algorithm):
    '''
    This function calculates the average number of assignments and conditionals
    for a given sorting algorithm of 100 random vectors whose size is specified by the array "vector_size"
    
    Inputs: sorting_algorithm -- which of three algorithms (either bubblesort, insertion sort, or quick sort) to use
    Outputs: mean_assignments -- np.array of average number of assignments for 100 vectors of sizes specified in "vector_size"
             mean_conditionals -- np.array of average number of conditionals for 100 vectors of sizes specified in "vector size"
    '''
    np.random.seed(1) #set seed of random number generator to 1, for reproducibility
    mean_assignments = np.zeros(10)
    mean_conditionals = np.zeros(10)
    for count, size in enumerate(vector_size): #loop specifying position and size of 100 vectors
        assignments = np.zeros(100) #creating array to store future assignment numbers
        conditionals = np.zeros(100) #creating array to store future conditional numbers 
        for v_num in range(100): #loop which creates vectors of calculated assignments and conditionals for 100 vectors of a given size
            vector = np.random.rand(size) #generating random vector of given size
            sorted_array, assignment, conditional = sorting_algorithm(vector) #sorting vector based on sorting algorithm
            assignments[v_num] = assignment #storing assignment number in assignments vector
            conditionals[v_num] = conditional #storing conditional number in conditionals vector
        mean_assignments[count] = assignments.mean() #stores average number of assignments in mean_assignments
        mean_conditionals[count] = conditionals.mean() #stores average number of conditionals in mean_conditionals
        print("Finished calculations for vectors of size:",size)
                
    return mean_assignments, mean_conditionals<jupyter_output><empty_output><jupyter_text>Bubblesort<jupyter_code>#Bubblesort implementation function
def bubblesort(array):
    '''
    This function sorts any given list of numbers from smallest to largest using the "bubble sort" algorithm.
    
    Inputs: array (array of numbers to be sorted)
    Outputs: sorted array, number of assignments, number of conditionals
    '''
    conditional = 0
    assignment = 0
    n = len(array) #total number of elements in array
    
    for i in range(n): #first loop: passes through whole list
        for j in range(n-i-1): #second loop: only compares elements in list that have "bubbled" to the top already/you know are correct
            conditional = conditional + 1 #counts conditionals--assuming I'm counting whenever comparison happens (not that it's true)
            if array[j] > array[j+1]: ##if the first element in the pair is bigger than the second element in the pair...
                ##swap them!
                array[j], array[j+1] = array[j+1], array[j] #switches the position of the first and second element in the pair
                assignment = assignment + 2 #counts 2 assignments per swap--assume both values are being moved
            
    return array, assignment, conditional
#testing to make sure algorithm works
sorted_array, assignment, conditional = bubblesort(np.array([3,2,1,5,7,8]))
print(sorted_array)
print("The number of assignments are:",assignment)
print("The number of conditionals are: ",conditional)
bubble_assignments, bubble_conditionals = t_complexity(bubblesort) #returning average assignment and conditional number
#for bubble sort on different size vectors
print(bubble_assignments) #average number of assignments, corresponding to vectors of size "vector_size"
print(bubble_conditionals) #average number of conditionals, corresponding to vectors of size "vector_size"<jupyter_output>[  4883.48  19997.86  45118.26  79680.08 124768.46 180129.34 244436.24
 320271.1  404611.54 498828.24]
[  4950.  19900.  44850.  79800. 124750. 179700. 244650. 319600. 404550.
 499500.]<jupyter_text>Insertion Sort<jupyter_code>#insertion sort implementation function
def insertionsort(array):
    '''
    This function sorts any given array of numbers from smallest to largest using the "insertion sort" algorithm.
    
    Inputs: array (array of numbers to be sorted)
    Outputs: sorted array, number of assignments, number of conditionals
    '''
    conditional = 0 
    assignment = 0
    n = len(array) #total number of elements in array
    

            
    for i in range(1, n): #go through whole array
        temp = array[i] #assign current place in array as temporary variable
        j = i-1 #assign index you will compare temporary variable to as one element to the left
        while True: #continue to compare and swap until "if" conditions aren't met
            conditional = conditional + 1 #counts conditional of checking that j is greater than 0
            if j >= 0: True #checking if you hit the first element in the array
            else:
                break
            conditional = conditional + 1 #count conditional of comparing value and temp
            if array[j] > temp: #checking if the comparison element is larger than temporary variable. If so, then:
                array[j], array[j+1] = array[j+1], array[j] #swap
                j = j-1 #increment the comparison element to be one lower
                assignment = assignment + 2 #count assignment
            else:
                break
        array[j+1] = temp #assign element as new temporary variable
        assignment = assignment + 1 #count assignment
        
        
            
    return array, assignment, conditional
            
#testing that insertion sort algorithm function works
insertion_sorted_array, insertion_assignment, insertion_conditional = insertionsort([4,1,2,3])
print(insertion_sorted_array)
print("The number of assignments are:",insertion_assignment)
print("The number of conditionals are: ",insertion_conditional)
insertion_assignments, insertion_conditionals = t_complexity(insertionsort) #returning average assignment and conditional number
#for insertion sort on different size vectors
print(insertion_assignments)
print(insertion_conditionals)<jupyter_output>[  4982.48  20196.86  45417.26  80079.08 125267.46 180728.34 245135.24
 321070.1  405510.54 499827.24]
[  5077.45  20390.98  45711.01  80472.47 125760.51 181321.34 245828.06
 321863.07 406402.89 500820.07]<jupyter_text>Quick sort To implement quick sort, I based my own code on the psuedo-code seen here: https://www.geeksforgeeks.org/quick-sort/<jupyter_code>def partition(array, start, end):
    '''
    This function partitions an array of numbers from smallest to largest by picking a pivot element and ensuring
    that all smaller elements are below pivot and higher elements are above pivot.
    
    Inputs: array -- array of numbers to be partitioned
            start -- starting index of array (smaller pointer)
            end -- ending index of array
    Outputs: i + 1 -- incremented index of smaller pointer
    '''
    #because my quicksort() function is recursive, I am using global variables to initialize
    #my conditional and assignment variable outside the function
    global conditional
    global assignment

    i = (start - 1)  #index of smaller pointer
    pivot = array[end]  #pivot
  
    for j in range(start , end): #j represents the "larger pointer"
        conditional = conditional + 1 #count conditional
        if   array[j] < pivot: #if larger pointer is smaller than pivot:
            i = i + 1 #increase index of smaller point and...
            array[i], array[j] = array[j], array[i] #swap elements!
            assignment = assignment + 2 #count assignment
            
    array[i+1], array[end] = array[end], array[i+1] #swap pivot and increment small pointer
    assignment = assignment + 2 #count assignment
    return (i+1)             


def quicksort(array, start, end):
    '''
    This function sorts any given array of numbers from smallest to largest using the "quick sort" algorithm,
    which is the recusrive implementation of the partition() function.
    
    Inputs: array -- array of numbers to be partitioned
            start -- starting index of array (smaller pointer)
            end -- ending index of array
            
    Outputs: sorted array, number of assignments, number of conditionals
    '''
    global conditional
    global assignment
    
    conditional = conditional + 1 #count conditional
    if start < end:
        p = partition(array, start, end) #defining p as the index which we are partitioning at
        
        #next two lines sort elements preceding and following the partition p
        quicksort(array, start, p - 1) 
        quicksort(array, p + 1, end)
    
    return array, assignment, conditional

        
#note: I have to initialize assignment and conditional here because my function is recursive
assignment = 0 
conditional = 0

#testing to see if my quick sort function works
test_array = np.array([5,6,2,0,5,8,9])
n = len(test_array)

quick_sorted_array, assignment, conditional = quicksort(test_array, 0, n-1)
print(quick_sorted_array)
print("The number of assignments are:",assignment)
print("The number of conditionals are: ",conditional)
#need a new t_complexity function that can deal with quick sort algorithm,
#since it requires global variables and additional inputs start and end
vector_size = np.array([100, 200, 300, 400, 500, 600, 700, 800, 900, 1000])

def t_complexity_quick(sorting_algorithm):
    '''
    This function calculates the average number of assignments and conditionals
    for a given sorting algorithm of 100 random vectors whose size is specified by the array "vector_size"
    
    Inputs: sorting_algorithm -- which of three algorithms (either bubblesort, insertion sort, or quick sort) to use
    Outputs: mean_assignments -- np.array of average number of assignments for 100 vectors of sizes specified in "vector_size"
             mean_conditionals -- np.array of average number of conditionals for 100 vectors of sizes specified in "vector size"
    '''
    #next two lines allow conditional and assignment to be global variables since they're global in the quicksort function
    global conditional
    global assignment 
    np.random.seed(1) #set seed of random number generator to 1, for reproducibility
    mean_assignments = np.zeros(10)
    mean_conditionals = np.zeros(10)
    for count, size in enumerate(vector_size): #loop specifying position and size of 100 vectors
        assignments = np.zeros(100) #creating array to store future assignment numbers
        conditionals = np.zeros(100) #creating array to store future conditional numbers
        for v_num in range(100): #loop which creates vectors of calculated assignments and conditionals for 100 vectors of a given size
            #next two lines initialize/"reblank" my assignment and conditional variables for each vector
            assignment = 0
            conditional = 0
            vector = np.random.rand(size) #generating random vector of given size
            n = len(vector)
            sorted_array = sorting_algorithm(vector, 0, n-1) #sorting vector based on sorting algorithm
            assignments[v_num] = assignment #storing assignment number in assignments vector
            conditionals[v_num] = conditional #storing conditional number in conditionals vector
        mean_assignments[count] = assignments.mean() #stores average number of assignments in mean_assignments
        mean_conditionals[count] = conditionals.mean() #stores average number of conditionals in mean_conditionals
        print("Finished calculations for vectors of size:",size)
                
    return mean_assignments, mean_conditionals
quick_assignments, quick_conditionals = t_complexity_quick(quicksort) #returning average assignment and conditional number
#for quick sort on different size vectors
print(quick_assignments)
print(quick_conditionals)<jupyter_output>[  800.92  1841.72  2995.68  4248.48  5598.3   6756.1   8137.02  9610.58
 10755.5  12313.34]
[  782.32  1839.98  2972.16  4240.75  5505.75  6791.32  8090.52  9487.37
 10926.97 12283.19]<jupyter_text>Graphs of stuffs Here, I am now plotting the time complexity results of all my algorithms as a summary and to prove the O() values of bubble and quick sort.<jupyter_code>#plot of bubblesort assignments and conditionals with varying array length
f, ax = plt.subplots(figsize = [12, 10])
sns.lineplot(x=vector_size, y = bubble_assignments, label ="bubble sort assignments", markers = True, marker ="o") #bubble assignments
sns.lineplot(x=vector_size, y = bubble_conditionals, label ="bubble sort conditionals", markers = True, marker ="o") #bubble conditionals
sns.lineplot(x=vector_size, y = vector_size ** 2, label = "N^2", markers = True, marker ="o") #N^2 comparison
ax.set(xlabel = 'Array Size', ylabel = 'Run Time (execution counts)', title = 'Plot of Vector Size vs. Run Time',
      xticks = np.arange(0, 1100,100));<jupyter_output><empty_output><jupyter_text>Note that "bubble sort assignments"--in blue--is  underneath the green "N^2" line, which is why you can't see it on the graph. However, is serves as convincing evidence that bubble sort is indeed O(N^2).<jupyter_code>for index in range(len(vector_size)):
    print("For a",vector_size[index],"sized-array, the average number of assignments is", bubble_assignments[index], "and conditionals is", bubble_conditionals[index], "for bubble sort")<jupyter_output>For a 100 sized-array, the average number of assignments is 4883.48 and conditionals is 4950.0 for bubble sort
For a 200 sized-array, the average number of assignments is 19997.86 and conditionals is 19900.0 for bubble sort
For a 300 sized-array, the average number of assignments is 45118.26 and conditionals is 44850.0 for bubble sort
For a 400 sized-array, the average number of assignments is 79680.08 and conditionals is 79800.0 for bubble sort
For a 500 sized-array, the average number of assignments is 124768.46 and conditionals is 124750.0 for bubble sort
For a 600 sized-array, the average number of assignments is 180129.34 and conditionals is 179700.0 for bubble sort
For a 700 sized-array, the average number of assignments is 244436.24 and conditionals is 244650.0 for bubble sort
For a 800 sized-array, the average number of assignments is 320271.1 and conditionals is 319600.0 for bubble sort
For a 900 sized-array, the average number of assignments is 404611.54 and conditionals is 4[...]<jupyter_text>The graph and numbers here suggest that bubble sort has a O(n^2), as the number of conditionals/assignments appear to be increasing quadratically with array size. This can also be checked by seeing if the ratio (number of assignments/N^2)--where N is the size of the array--is constant. Indeed, we show that is is (with a value of ~0.5) below:<jupyter_code>ratio = bubble_assignments/(vector_size**2)
f, ax = plt.subplots(figsize = [12, 10])
sns.lineplot(x=vector_size, y = ratio, markers = True, marker ="o")
ax.set(xlabel = 'Array Size', ylabel = '(# assignments/N^2)',
      xticks = np.arange(0, 1100,100),
      yticks = np.arange(0.4, 0.7, 0.1));
#plot of insertion sort assignments and conditions with varying array length
f, ax = plt.subplots(figsize = [12, 10])
sns.lineplot(x=vector_size, y = insertion_assignments, label="insertion sort assignments", markers = True, marker ="o")
sns.lineplot(x=vector_size, y = insertion_conditionals, label="insertion sort conditionals", markers = True, marker ="o")
sns.lineplot(x=vector_size, y = vector_size ** 2, label = "N^2", markers = True, marker="o") #N^2 comparison
ax.set(xlabel = 'Array Size', ylabel = 'Run Time (execution counts)', title = 'Plot of Vector Size vs. Run Time',
      xticks = np.arange(0, 1100,100));
for index in range(len(vector_size)):
    print("For a",vector_size[index],"sized-vector, the average number of assignments is", insertion_assignments[index], "and conditionals is", insertion_conditionals[index], "for insertion sort")
#plot of quicksort assignments and conditional with varying array length
f, ax = plt.subplots(figsize = [12, 10])
sns.lineplot(x=vector_size, y = quick_assignments, label="quick sort assignments", markers = True, marker ="o")
sns.lineplot(x=vector_size, y = quick_conditionals, label="quick sort conditionals", markers = True, marker ="o")
sns.lineplot(x=vector_size, y = vector_size * np.log(vector_size), label = "N*log(N)", markers = True, marker="o") #N*log(N) comparison
ax.set(xlabel = 'Array Size', ylabel = 'Run Time (execution counts)', title = 'Plot of Vector Size vs. Run Time',
      xticks = np.arange(0, 1100,100));<jupyter_output><empty_output><jupyter_text>The green line--which corresponds with Nlog(N) appears to have a different slope (although similar overall shape)--to the quick sort assignments and conditionals. I need further evidence (which I present a few cells down) to prove that this algorithm is indeed Nlog(N).<jupyter_code>for index in range(len(vector_size)):
    print("For a",vector_size[index],"sized-vector, the average number of assignments is", quick_assignments[index], "and conditionals is", quick_conditionals[index], "for insertion sort")<jupyter_output>For a 100 sized-vector, the average number of assignments is 800.92 and conditionals is 782.32 for insertion sort
For a 200 sized-vector, the average number of assignments is 1841.72 and conditionals is 1839.98 for insertion sort
For a 300 sized-vector, the average number of assignments is 2995.68 and conditionals is 2972.16 for insertion sort
For a 400 sized-vector, the average number of assignments is 4248.48 and conditionals is 4240.75 for insertion sort
For a 500 sized-vector, the average number of assignments is 5598.3 and conditionals is 5505.75 for insertion sort
For a 600 sized-vector, the average number of assignments is 6756.1 and conditionals is 6791.32 for insertion sort
For a 700 sized-vector, the average number of assignments is 8137.02 and conditionals is 8090.52 for insertion sort
For a 800 sized-vector, the average number of assignments is 9610.58 and conditionals is 9487.37 for insertion sort
For a 900 sized-vector, the average number of assignments is 10755.5 and con[...]<jupyter_text>To verify that the big-O for quick sort is O(nlog(n)), I checked that the ratio (number of assignments/Nlog(N)) showed a relatively constant value. It did, with a value a bit above 1.7, proving quick sort does have a O(nlog(n)).<jupyter_code>ratio = quick_assignments/(vector_size*np.log(vector_size))
f, ax = plt.subplots(figsize = [12, 10])
sns.lineplot(x=vector_size, y = ratio, markers = True, marker ="o")
ax.set(xlabel = 'Array Size', ylabel = '(# assignments/N*log(N))',
      xticks = np.arange(0, 1100,100),
      yticks = np.arange(1.5, 2.2, 0.1));<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07824466984061271, 'fraction_numerical': 0.04905816601117781, 'mean_word_length': 3.8899291497975708, 'pattern_counts': {'":': 0, '<': 39, '<?xml version=': 0, '>': 40, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '557584', 'license': 'Apache-2.0', 'n_tokens_mistral': 6064, 'n_tokens_neox': 5265, 'n_words': 2209, 'path': 'SierraLear_BMI203_HW1.ipynb', 'repo_name': 'sierralear/BMI-203-HW1', 'size': '19329'}