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)
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)
- I will locate the smallest number in the list and place it at the beginning. Subsequently, I will disregard that number and repeat the procedure until the list is sorted.
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?
It compares consecutive elements and sorts in a linear fashion.
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 and be ready to explain it to your other group members.
Practice
[75, 17, 46, 80, 67, 45, 69, 79, 40, 0]
Would you sort this list with...
- Bubble Sort
-
Selection SortSelection sort because it would be faster since the 0 and 75 would swap, making it closer to being sorted quicker.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
Would you sort this list with...
- Merge Sort
-
`Insertion Sort</mark>Insertion because it has a faster time complexity than if merge sort was used.
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 sort because you would only move one thing.
- [Elephant, Banana, Cat, Dog, Apple]
Selection sort because it would only take one pass
- [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 a long list. Select the algorithm you believe is best for each, explain.
- [0, 2, 6, 4, 8, 10]
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?
List and dictionary are categorized as collection types instead of primitive types. They utilize sophisticated data structures and algorithms compared to primitive types. In Python, a list is commonly implemented as a dynamic array, while a dictionary is typically implemented using a hash table. These data structures and algorithms are more intricate compared to those employed for primitive types, hence the classification of list and dictionary as collection types.
- 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 passed by reference, not by value. When a variable is passed as an argument to a function, a reference to the object is passed, not a copy of the object itself.
- 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, do NOT make a copy my list when doing this
- 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
# Selection sort [Arrays]
def selectionSort1(arr): # takes in an array
for i in range(len(arr)): # first iteration
min_idx = i
for j in range(i+1, len(arr)): # second iteration
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
num1 = [9, 33, 17, 26, 44, 12]
str1 = ["pasta", "chicken", "pizza", "wings", "nachos", "burger"]
num2 = [100, 50, 20, 24, 54, 26, 82, 1, 98, 399]
str2 = ["dog", "cat", "bird", "hamster", "fish", "turtle"]
print(selectionSort1(num1))
print(selectionSort1(str1))
print(selectionSort1(num2))
print(selectionSort1(str2))
# Selection sort [Dictionaries iterating through key's and values]
def selectionSort2(lst, key):
n = len(lst)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if lst[j][key] < lst[min_idx][key]:
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
return lst
# function for displaying neatly
def display(lst, key):
sorted_list = selectionSort2(lst, key)
print("Sorted by", key + ":")
for person in sorted_list:
print("\tItem:", person['item'])
print("\tRating:", person['rating'])
print("\tDescription:", person['Description'])
print("")
foodDictionary = [
{"item": "Chicken", "rating": 10, "Description": "Chicken"},
{"item": "Pasta", "rating": 6, "Description": "Pasta"},
{"item": "Salad", "rating": 3, "Description": "Salad"},
{"item": "Burger", "rating": 8, "Description": "Burger"}
]
key_row = foodDictionary[0]
for key in key_row:
display(foodDictionary, key)
"""
* 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("Sorted by " + key)
bubbleSort(list_of_people, key) # sort list of people
print(list_of_people)