Sorting Algorithms Notes and Hacks
Working with Data Structures and manipulating data.
import random
numbers = []
for i in range(10):
numbers.append(random.randint(0,100))
print("Random List")
print(numbers)
Explore
Get into groups of 3
We will be focusing on 4 algorithms today.
We will look at the first one together, Bubble Sort
What is happening with this sort?
In your groups you will each choose to be an expert on a sorting algorithm. Merge, Selection, and Insertion. Take about 5 minutes to read about your algorithm (Geek for Geeks linked below) and be ready to explain it to your other group members.
Practice
[75, 17, 46, 80, 67, 45, 69, 79, 40, 0]
How would you sort this list with...
- Bubble Sort
- This works by repeatedly swapping elements if they are in the wrong order. It continues iterating through the list until the entire list is sorted.
Pass 1: [17, 46, 75, 67, 45, 69, 79, 40, 0, 80]
Pass 2: [17, 46, 67, 45, 69, 75, 40, 0, 79, 80]
Pass 3: [17, 46, 45, 67, 69, 40, 0, 75, 79, 80]
Pass 4: [17, 45, 46, 67, 40, 0, 69, 75, 79, 80]
Pass 5: [17, 45, 46, 40, 0, 67, 69, 75, 79, 80]
Pass 6: [17, 45, 40, 0, 46, 67, 69, 75, 79, 80]
Pass 7: [17, 40, 0, 45, 46, 67, 69, 75, 79, 80]
Pass 8: [17, 0, 40, 45, 46, 67, 69, 75, 79, 80]
Pass 9: [0, 17, 40, 45, 46, 67, 69, 75, 79, 80]
- Selection Sort
- this works by repeatedly finding the minimum element from the unsorted part of the list and placing it at the beginning
Pass 1: [0, 17, 46, 80, 67, 45, 69, 79, 40, 75]
Pass 2: [0, 17, 40, 80, 67, 45, 69, 79, 46, 75]
Pass 3: [0, 17, 40, 45, 67, 80, 69, 79, 46, 75]
Pass 4: [0, 17, 40, 45, 46, 80, 69, 79, 67, 75]
Pass 5: [0, 17, 40, 45, 46, 67, 69, 79, 80, 75]
Pass 6: [0, 17, 40, 45, 46, 67, 69, 75, 80, 79]
Pass 7: [0, 17, 40, 45, 46, 67, 69, 75, 79, 80]
Explain.
Pt2
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort recursively divides the list into smaller halves, sorts them individually, and then merges them back together to obtain the final sorted list.
Step 1:Divide the list into individual elements [88], [39], [53], [39], [58], [43], [74], [81], [71], [51] Step 2: Merge the individual elements pairwise [39, 88], [39, 53], [39, 53, 88], [39, 39, 53, 53, 88], [43, 58], [43, 58, 74], [43, 58, 74, 81], [51, 71], [51, 71, 81], [51, 71, 74, 81]
Step 3: Merge the pairs until we obtain the final sorted list [39, 39, 53, 53, 58, 88], [43, 58, 74, 74, 81], [51, 71, 71, 81]
Final sorted list: [39, 39, 43, 51, 53, 53, 58, 71, 74, 74, 81, 81, 88]
- Insertion Sort iterates over each element in the unsorted portion and inserts it into the correct position in the sorted portion.
Pass 1: [39, 88, 53, 39, 58, 43, 74, 81, 71, 51]
Pass 2: [39, 53, 88, 39, 58, 43, 74, 81, 71, 51]
Pass 3: [39, 39, 53, 88, 58, 43, 74, 81, 71, 51]
Pass 4: [39, 39, 53, 58, 88, 43, 74, 81, 71, 51]
Pass 5: [39, 39, 43, 53, 58, 88, 74, 81, 71, 51]
Pass 6: [39, 39, 43, 53, 58, 74, 88, 81, 71, 51]
Pass 7: [39, 39, 43, 53, 58, 74, 81, 88, 71, 51]
Pass 8: [39, 39, 43, 53, 58, 71, 74, 81, 88, 51]
Pass 9: [39, 39, 43, 53, 58, 71, 74, 81, 88, 51]
Pass 10: [39, 39, 43, 51, 53, 58, 71, 74, 81, 88]
import nltk
import random
nltk.download('words') # Download the word list (only required once)
from nltk.corpus import words
english_words = words.words()
#print(len(english_words)) # Prints the number of words in the list
# You can now use the 'english_words' list in your code
words = []
for i in range(10):
words.append(english_words[random.randint(0,len(english_words))])
print("Random List")
print(words)
Discuss
Answer the following with your group.
- When should you use each algorithm? What makes an algorithm the right choice?
- Given the following lists...
- [0, 2, 6, 4, 8, 10] - INSERTION because then only one sort is necessary OR bubble sort OR Bubble sort because it would just swap 4 and 6
- [Elephant, Banana, Cat, Dog, Apple] - Selection sort because it finds the "least"/"first"
- [29, 13, 83, 47, 32, 78, 100, 60, 65, 15, 24, 9, 40, 68, 53, 8, 90, 58, 39, 32, 34, 91, 74, 94, 49, 87, 34, 87, 23, 17, 27, 2, 38, 58, 84, 15, 9, 46, 74, 40, 44, 8, 55, 28, 81, 92, 81, 88, 53, 38, 19, 21, 9, 54, 21, 67, 3, 41, 3, 74, 13, 71, 70, 45, 5, 36, 80, 64, 97, 86, 73, 74, 94, 79, 49, 32, 20, 68, 64, 69, 1, 77, 31, 56, 100, 80, 48, 75, 85, 93, 67, 57, 26, 56, 43, 53, 59, 28, 67, 50] - Merge sort because it's so long Select the algorithm you believe is best for each, explain.
Looking at saving time complexity! Looping through is O(N^2) Merging is N(logN)
HACKS
Provided below is a Bubble Sort Algorithm sorting a list of dictionaries based off of selected key.
Now it's time to do some coding...
Run code and then research and answer these questions...
- Is a list and/or dictionary in python considered a primitive or collection type? Why?
- Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
Implement new cell(s) and/or organize cells to do the following.
- Create your own list
- Use your expertise sorting algorithm (selection, insertion, merge). Note, I got my bubble sort from Geek for Geeks and made modifications. Each student in a group should have a unique algorithm.
- Test your list with my bubble sort
- Test my list with your new sort
- Research analysis on sorting:comparisons, swaps, time. Build this into your hacks. - Find a better way to print the data, key first, then other elements in viewable form.
Use the code below to help guide your adventure
"""
* Creator: Nighthawk Coding Society
Bubble Sort of a List with optimizations
"""
# bubble sorts a list of dictionaries, base off of provided key
def bubbleSort(list, key):
n = len(list) - 1 # list are indexed 0 to n-1, len is n
# Traverse through list with i index
for i in range(n):
swapped = False # optimize code, so it exits if now swaps on inner loop
# Inner traversal using j index
for j in range(n-i): # n-i as positions on right are in order in bubble
# Swap if the element KeyN is greater KeyN1
keyN = list[j].get(key)
keyN1 = list[j+1].get(key)
if keyN > keyN1:
swapped = True
list[j], list[j + 1] = list[j + 1], list[j] # single line swap
if not swapped: # if no swaps on inner pass, list is sorted
return # exit function
def insertionSort(list, key):
for i in range (1, len(list)):
keyN = list[i].get(key)
keyO = list[i]
# print(keyN)
j = i-1
keyJ = list[j].get(key)
# print(keyJ)
while j>=0 and keyN < keyJ:
list[j+1] = list[j]
j = j -1
list[j+1] = keyO
return list
if __name__ == "__main__":
# list/dictionary sample
list_of_people = [
{"name": "Risa", "age": 18, "city": "New York"},
{"name": "John", "age": 63, "city": "Eugene"},
{"name": "Shekar", "age": 18, "city": "San Francisco"},
{"name": "Ryan", "age": 21, "city": "Los Angeles"}
]
# assuming uniform keys, pick 1st row as source of keys
key_row = list_of_people[0]
# print list as defined
print("Original")
print(list_of_people)
# for key in key_row: # finds each key in the row
# print(key)
# bubbleSort(list_of_people, key) # sort list of people
# insertionSort(list_of_people, key)
# print(list_of_people)
print("\n-----------------------------")
print("Sorting by insertion sort...")
for key in key_row:
print("\nsorting by " + key)
print("insertion sort")
print(insertionSort(list_of_people, key))
def mergeSort(arr, key):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = mergeSort(left, key)
right = mergeSort(right, key)
return merge(left, right, key)
def merge(left, right, key):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i].get(key) <= right[j].get(key):
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
while i < len(left):
merged.append(left[i])
i += 1
while j < len(right):
merged.append(right[j])
j += 1
return merged
if __name__ == "__main__":
# list/dictionary sample
list_of_people = [
{"name": "Tom Brady", "age": 50, "team": "Patriots"},
{"name": "Mahomes", "age": 27, "team": "Chiefs"},
{"name": "Justin Jefferson", "age": 23, "team": "Vikings"},
]
# assuming uniform keys, pick the first row as the source of keys
key_row = list_of_people[0]
# print the list as defined
print("original")
print(list_of_people)
for key in key_row: # find each key in the row
print(key)
sorted_list = mergeSort(list_of_people, key) # sort the list of people
print(sorted_list)
Comparison: The merge sort algorithm utilizes comparisons to establish the relative arrangement of elements during the merging phase. These comparisons are executed based on a specified key or attribute associated with the elements undergoing sorting.
Swaps: Unlike other sorting algorithms, merge sort does not directly employ swaps to rearrange elements. Instead, the merging process in merge sort involves the creation of new lists or arrays to hold the sorted elements. The elements from the original list are selectively positioned in the appropriate locations within the newly merged list.
Time: The time complexity of an algorithm estimates how its performance scales with the size of the input. In the case of merge sort, it exhibits a time complexity of O(n log n), where n represents the number of elements in the list. Consequently, when the size of the list doubles, the time required to sort it will increase by a factor of approximately two times the logarithm of the list size.
def mergeSort(arr, key):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = mergeSort(left, key)
right = mergeSort(right, key)
return merge(left, right, key)
def merge(left, right, key):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i].get(key) <= right[j].get(key):
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
while i < len(left):
merged.append(left[i])
i += 1
while j < len(right):
merged.append(right[j])
j += 1
return merged
if __name__ == "__main__":
# list/dictionary sample
list_of_people = [
{"name": "Tom Brady", "age": 50, "team": "Patriots"},
{"name": "Mahomes", "age": 27, "team": "Chiefs"},
{"name": "Justin Jefferson", "age": 23, "team": "Vikings"},
]
# assuming uniform keys, pick the first row as the source of keys
key_row = list_of_people[0]
print("Original:")
for person in list_of_people:
print(person)
print("\nSorted by Name:")
sorted_list = mergeSort(list_of_people, "name")
for person in sorted_list:
print(person)
print("\nSorted by Age:")
sorted_list = mergeSort(list_of_people, "age")
for person in sorted_list:
print(person)
print("\nSorted by team:")
sorted_list = mergeSort(list_of_people, "team")
for person in sorted_list:
print(person)