Sorting Algorithms
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)
print(sorted(numbers))
Warm Up
Discuss with a partner... What are some strategies you would use to sort this list? (Don't worry about writing code for now)
- sort them from least to greatest, greatest to least, or evens and odds. Compare the one item to the list to the next item in the list, then going one item over and doing the same thing.
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.
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)
print(sorted(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] bubble sort or insertion sort because it only has one switch needed
- [Elephant, Banana, Cat, Dog, Apple] selection because it only needs to swap the first and last element
- [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 has a time complexity of O(n log n) Select the algorithm you believe is best for each, explain.
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?
- A list and dictionary in python are both considered as collection types. This is because primative types could not be split into smaller sub-divisions, however, lists and dictionaries could be split into their atomic units and both serve to group together similar data.
- Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
- The list passed into bubble sort is "pass-by-reference". This is because we directly input the list that we want to sort into the bubleSort function without creating any copies of it. Thus, our function will sort the array in place and modify the original array.
- Is a list and/or dictionary in python considered a primitive or collection type? Why?
-
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
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
print(list_of_people)
from random import randint
scores = [randint(1,100) for _ in range(25)]
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"}
]
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
L = merge_sort(L)
R = merge_sort(R)
return merge(L, R)
def merge(left, right):
sorted = []
l_idx = r_idx = 0
while l_idx < len(left) and r_idx < len(right):
if left[l_idx] <= right[r_idx]:
sorted.append(left[l_idx])
l_idx += 1
else:
sorted.append(right[r_idx])
r_idx += 1
sorted.extend(left[l_idx:])
sorted.extend(right[r_idx:])
return sorted
def bubbleSortList(list_of_people):
n = len(list_of_people) - 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_of_people[j]
keyN1 = list_of_people[j+1]
if keyN > keyN1:
swapped = True
list_of_people[j], list_of_people[j + 1] = list_of_people[j + 1], list_of_people[j] # single line swap
if not swapped: # if no swaps on inner pass, list is sorted
return # exit function
scores1 = scores
print("Original: ", scores)
print("Teacher provided algorithm: ", bubbleSortList(scores))
print("My mergesort algorithm: ", merge_sort(scores1))