Instantly share code, notes, and snippets.

# Integralist/0. Algorithms in Python.md

Last active March 3, 2022 08:51
Show Gist options
• Save Integralist/9763bded76e7d826535a3caeafc3bdff to your computer and use it in GitHub Desktop.
Algorithms in Python (modified from the excellent: Grokking Algorithms) - see also http://www.integralist.co.uk/posts/bigo.html for details on understanding Big O notation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ''' Binary Search algorithm Description: Locate an item within a collection by using a divide and conquer approach. In essence, pick the middle of the collection then verify if the value is too high or low and then reduce the sliding window, now pick the middle again - rinse/repeat Performance: O(Log₂ n) Logarithmic time Meaning: 12 item collection will take (worst case) ~4 steps to locate the specified index using binary search Note: collection must be sorted ''' collection = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 20, 21] # 12 items def binary_search(collection, item): print("we're looking for:", item, "\n") print("collection:", collection, "\n") start = 0 stop = len(collection) - 1 while start <= stop: middle = round((start + stop) / 2) guess = collection[middle] print("start: {}\nstop: {}\nmiddle: {}\nguess: {}\n".format(start, stop, middle, guess)) if guess == item: return middle if guess > item: stop = middle - 1 else: start = middle + 1 return None print(binary_search(collection, 9)) # found at index: 4
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ''' Selection Sort algorithm Description: Sorts an unordered list by looping over the list n number of times and for each loop identifying either the smallest or largest element (which one depends on how you're hoping to sort your list: do you want ascending or descending order) You'll end up constructing a new ordered list Performance: O(n x n) O(n₂) Both forms are equivalent. You effectively loop a number of times to match collection length Then you loop the collection looking for smallest/largest Then you mutate the collection so it's smaller by one So although you're looping over the collection multiple times, you are in fact looping over a slightly smaller collection each time Although in reality the notation should be: O(n x n - 1) But that is invalid Big O notation, so we use the O(n₂) or O(n x n) instead If your collection is 10 items long then this calculates as: 10 * 10 (i.e. 10 to the power of 2) = 100 operations 0.1 * 100 = 10 seconds Note: to test algorithm in a different order, the quickest change is to turn < into > within the find_smallest function. This would cause program to return [9, 5, 3, 1] ''' def find_smallest(arr): smallest = arr[0] smallest_index = 0 for i, _ in enumerate(arr): if arr[i] < smallest: smallest = arr[i] smallest_index = i return smallest_index def selection_sort(arr): temp = [] for i in range(len(arr)): smallest = find_smallest(arr) temp.append(arr.pop(smallest)) return temp print(selection_sort([5, 9, 3, 1])) # [1, 3, 5, 9]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ''' Quick Sort algorithm Description: Sorts an unordered list using recusion and specifically using the D&C (Divide and Conquer) approach to problem solving Explanation: You pick a 'pivot' (a random array index) You loop the array storing items less than the pivot You loop the array storing items greater than the pivot Assume less and greater are already sorted You can now return 'less' + pivot + 'greater' In reality you'll use recursion to then sort both the less and greater arrays using the same algorithm Performance: Worst case: O(n x n) O(n₂) If collection is 10 items in length (10 * 10 = 100 operations) Best case: O(n Log₂ n) If collection is 10 items in length (10 * 4 (Log₂10 == 2*2*2*2) = 40 operations) Quick Sort's performance depends on the pivot you choose In our example code we always pick the zero index as it makes the code simpler, but not necessarily the most performant Notes: The following implementation doesn't pick a pivot at random It instead grabs the first index ''' def quicksort(arr): if len(arr) < 2: return arr else: pivot = arr[0] less = [i for i in arr[1:] if i <= pivot] greater = [i for i in arr[1:] if i > pivot] return quicksort(less) + [pivot] + quicksort(greater) print(quicksort([10, 5, 2, 3, 7, 0, 9, 12])) # [0, 2, 3, 5, 7, 9, 10, 12]
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ''' Notes: The following implementation doesn't pick a pivot at random It instead grabs the middle index ''' items = [10, 5, 2, 3, 7, 0, 9, 12] print("Original:", items) def quicksort(arr): if len(arr) < 2: return arr else: middle = round(len(arr) / 2) # grab the middle index pivot = arr.pop(middle) less = [i for i in arr if i <= pivot] greater = [i for i in arr if i > pivot] return quicksort(less) + [pivot] + quicksort(greater) print("Sorted: ", quicksort(items)) """ Original: [10, 5, 2, 3, 7, 0, 9, 12] Sorted: [0, 2, 3, 5, 7, 9, 10, 12] """
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ''' Notes: The following implementation picks a pivot at random As it should be, per the original definition of the algorithm's design ''' from random import randrange items = [10, 5, 2, 3, 7, 0, 9, 12] print("Original:", items) def quicksort(arr): if len(arr) < 2: return arr else: middle = randrange(0, len(arr)) # grab a random index pivot = arr.pop(middle) less = [i for i in arr if i <= pivot] greater = [i for i in arr if i > pivot] return quicksort(less) + [pivot] + quicksort(greater) print("Sorted: ", quicksort(items)) """ Original: [10, 5, 2, 3, 7, 0, 9, 12] Sorted: [0, 2, 3, 5, 7, 9, 10, 12] """
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters