<jupyter_start><jupyter_text>Before We begin, please fill out this quick survey to get a better sense of how we are doing in CoffeeBytes and of were you guys are at knowledge wise so far.-------------------------------------------------------------------------------[Super Cool Survey Link](https://enrique266012.typeform.com/to/FFaemv)---------------------------------------------------------- For this lesson, we will be implementing two well known algorithms: Binary Search and Quick Sort!--Binary Search -------------- Runtime: Worst case: O(log(n)) VERY FAST- Cons: Requires a pre-sorted array to work.Quick Sort------------ Average Case: O(nlog(n)) PRETTY FAST- Cons: Runtime Worse Case: O(n^2)- If we choose the pivot randomly, we can  ensure an O(log(n)) time operation (statistically speaking)  Quick Sort is a Divide and Conquer Algorithm. What does that mean? It means recursion! Quick Sort Algorithm: Steps on how it works:1. Pick an element, called a pivot, from the list.2. Partitioning: reorder the list so that all elements with values less than the pivot go left, while all elements with values greater than the pivot go right (equal values can go either way). Keep in mind, that the pivot is NOT in the middle of the partition after this. It is only used for comparison. This whole operation is called the partition operation.3. Recursively apply the above steps to the sub-list of elements with smaller values and separately to the sub-list of elements with greater values.![alt text](https://miro.medium.com/max/600/1*DtH6fEdBhoUGnjBWudJ8pA.png) [Video Link of video explanation](https://www.youtube.com/watch?time_continue=25&v=SLauY6PpjW4) Step 1: Implement the partition!-----<jupyter_code># partition takes in 4 arguments: a list (A), a left cursor, a right cursor, and the pivot
def partition(A, left, right, pivot):
    '''
    This is where most of the work for quicksort occurs.

    Partition() will iterate through the list A, moving the left
    cursor to the right until it reaches an element greater than
    the pivot. 
    
    Partition() will then iterate through A, moving the right cursor
    to the left until it reaches an element less than the pivot.

    Partition() will then swap the elements at the left and right
    cursors, thus "partitioning" the list swap by swap.
    
    This will all continue until the left and right cursors overlap, 
    which means all the values less than the pivot are on the left
    and all the elements greater than the pivot are on the right.

    Finally, partition() returns the index in the middle of this "partition".
    Get it? ;D
    
    Lets walk through this code line by line to get a better idea of how this works
    '''
    # Overall loop that will go through the whole list
    while (left <= right):
      
        # This loop will move the pointer UNTIL it reachs a value greater than the pivot 
        while(A[left] < pivot):
            left += 1
            
        # This loop will move the pointer UNTIL it reachs a value less than the pivot
        while(A[right] > pivot):
            right -= 1
            
        # This check is just to catch if we are overlapping cursors already!
        if(left <= right):
          
            # This syntax looks wack, but don't panic. This just swaps A[left] and A[right]
            A[left], A[right] = A[right], A[left]
            
            # Move the cursors after the swap.
            left += 1
            right -= 1
            
    # Finally, we return the partition point between the lesser values and the greater values
    # Turns out, its the left cursor! (Once we iterate through the above, of course)
    return left<jupyter_output><empty_output><jupyter_text>Step 2: Implement the Recursive QuickSort!-----------<jupyter_code># This is how python gets outside libraries (a bunch of code that we can use written by other people). Here, we require the "random" library so we can pick our pivot!
import random as random

# quicksort takes in 3 arguments: a list (A), a left cursor, and a right cursor
def quicksort(A, left, right):
    '''
    Quicksort() is the recursive portion of our entire algorithm.

    Quicksort() first checks if the left and right cursors are overlapping
    (in which case it returns out of the function).

    Quicksort() then generates a random pivot and passes it to our partition()
    function. 

    Partition() will take in the pivot and return the partition point we need to 
    split our list up into two halves.

    Finally, Quicksort() calls itself for the left half, and the right half,
    effectively doing the exact thing we just did but for these two sub lists. DONZO!

    We don't return anything here because we are modifying the list as we go, so
    we dont need to! 
    
    Lets walk through this line by line.
    '''

    # This just checks if we are overlapping our cursors, in which case, we are done!
    if left >= right:
        return

    # Here we use the random library's .choice() function to get a random element from the list
    pivot = random.choice(A)

    # We use partition() to get the partition point after moving elements around correctly
    p = partition(A, left, right, pivot)

    # Recurse on the left of p,
    quicksort(A, left, p - 1)
    
    # And on the right of p!
    quicksort(A, p, right)<jupyter_output><empty_output><jupyter_text>Step 3: Create an Interface!-----------<jupyter_code># qsort() takes one argument: a list! (A) Simple and clean <3
def qsort(A):
    '''
    This function is so we can call our sort function without
    having to worry about lows and highs. 
    
    It's more intuitive to pass just the list we want to sort 
    into the function. This is an example of whats called an "interface" in programming.

    You'll see this often when you start to use Classes and Objects, so I figured
    I might as well expose you to it now! :D
    '''
    # here we just call our recursive quicksort function with a left cursor of 0 and a right cursor of len(A) - 1, the rightmost index. The whole ass list!
    quicksort(A, 0, len(A) - 1)<jupyter_output><empty_output><jupyter_text>Step 4: Test it!----<jupyter_code># Random list of integers
lst = [7, 3, 1, 2, 0, 5, 2]

# Fingers Crossed!
qsort(lst)

# *Sweats*
print(lst)<jupyter_output>[0, 1, 2, 2, 3, 5, 7]<jupyter_text>Binary Search is also a Divide and Conquer Algorithm to find an element in a list. It requires a sorted list, but thats fine since we now have a working sort algorithm :D (QuickSort) It finds an element in a list in O(log(n)) time, or returns False otherwise.--------1. Compare x with the middle element.2. If x matches with middle element, we return the mid index.3. Else If x is greater than the mid element, then x can only lie in right half subarray after the mid element. So we recurse for right half.4. Else (x is smaller) recurse for the left half.![alt text](https://www.java2blog.com/wp-content/uploads/2015/07/BinarySearchInJava-1.jpg) Step 1: Implement Binary Search Step by Step!---<jupyter_code># binarysearch() takes in 2 arguments: a list (A), and the item we wish to find!
def binarysearch(A, item):
    '''
    Binarysearch() is a fairly straightforward recursive function.

    Binarysearch() first checks if the length of A is zero, in which case
    it returns false, quitting its execution. Why? 
    
    Once we recurse down to a sub list of length 0, that means the element
    isn't in the list! No point in continuing recursion after that. 

    Binarysearch() then (if len(A) isn't 0) computes the midpoint of A.

    Binarysearch() checks if the midpoint value is equal to zero, in which case
    it returns the item (We found it!).

    If the middle point isn't the item we are looking for, binarysearch() 
    checks if the item is less than or greater than the midpoint value.

    If the item is less than the midpoint value, we recurse to the left side 
    of the midpoint, since the right of the list cannot contain our item.
    (assuming our list is sorted!)

    Else, our item must be greater than the midpoint value since we already checked for equality.
    In this case, we recurse to the right side of the midpoint since the left of the list 
    cannot contain our item. (You sorted this list first, right?)

    This causes a recursion of a smaller and smaller sub list until our item is found. 
    Not too crazy, I hope! :D 

    Let's walk through this function line by line to get a better idea of how this all works.
    '''

    # Here, we just check if the list length is zero, in which case we return false. The item isn't in the list!
    if len(A) == 0:
        return False

    # Our length is greater than zero, so lets get recursing!
    else:

        # First, lets get that crucial midpoint index
        midpoint = len(A)//2

        # Gotta check if that middle element is actually our item. If it is, return it!
        if A[midpoint] == item:
            return item

        # Darn, looks like we didn't get lucky... Gotta keep looking!
        else:

            # Here we check which side we will start recursing on based on if the item is less than or greater than the middle value
            if item < A[midpoint]:
                
                # Recurse on the left side of the list using list slicing!
                return binarysearch(A[:midpoint], item)

            # Since we already checked for equality and less than in the above code, the only other possibility is that item is greater!
            else:

                # Recurse on the right side of the list using list slicing!
                return binarysearch(A[midpoint+1:], item)<jupyter_output><empty_output><jupyter_text>Step 2: Test it!---<jupyter_code># Random list
test = [7, 5, 0, 1, 4, 3, 9, 21, 4]

# Lets use our new sort algo! :D
qsort(test)

# *Sweats again*
print(test)

# *Oh dear god please work*
print(binarysearch(test, 3))

# "His palms are sweaty, knees weak, arms are heavy"
print(binarysearch(test, 13))<jupyter_output>[0, 1, 3, 4, 4, 5, 7, 9, 21]
3
False
{'fraction_non_alphanumeric': 0.08531135167345318, 'fraction_numerical': 0.009335584467176482, 'mean_word_length': 2.8, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 25, 'https://': 4, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '533841', 'license': 'MIT', 'n_tokens_mistral': 2886, 'n_tokens_neox': 2690, 'n_words': 1465, 'path': 'CoffeeBytes_02_ACM.ipynb', 'repo_name': 'enrprz/CoffeeBytes', 'size': '10069'}