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)
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 (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
- I would compare the first two numbers. If one is less than the other, I would put the lesser number a the front. Then i would move on to the second and third digits. I would continue this process multiple times until I know that the entire list is ordered correctly.
- Selection Sort
- I would start with the first number and swap that with the least number. Then I would find the second number and swap that with the second least number. I would continue this until I was complete.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort
- I would split the entire list into groups of two numbers. Then I would sort each group of two. Then I would merge each group of two with another group of two. Then I would sort that group of four. I would continue this until my entire list was sorted.
- Insertion Sort
- I would sort the entire list until the lowest number is the first. Then I would continue this pattern until it goes from lowest to highest.
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, select the algorithm you believe is best for each, explain.
- [0, 2, 6, 4, 8, 10]
- Insertion Sort because it goes through each pair and compares them and swaps them. It would have to swap until the 3rd pair and after this swap, the list would be sorted properly.
- [Elephant, Banana, Cat, Dog, Apple]
- Selection Sort because it swaps the first item in the list with the lowest item. This means that Elephant would be swapped with Apple and after this change, the list would be sorted correctly.
- [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 you can easily split the list into pairs of numbers and the sorting of each pair runs in parallel which would reduce the time required to sort this list.
- [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?
- A list and a dictionary are considered collection types rather than primitive types. They are implemented using more complex data structures and algorithms than the primitive types. For example, a list in Python is typically implemented as a dynamic array, while a dictionary is usually implemented using a hash table. These data structures and algorithms are more complex than those used to implement primitive types, which is why they are considered 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
- 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
arr1 = [0, 2, 6, 4, 8, 10]
arr2 = ["Elephant", "Banana", "Cat", "Dog", "Apple"]
arr3 = [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]
arr4 = ["nike", "Adidas", "PUMA", "Under Armor"]
def merge_sort(arr):
# checks if array has a length of 1 or less (already sorted)
if len(arr) <= 1:
return arr
# finds midpoint
mid = len(arr) // 2
# splits into left half and right half
left_half = arr[:mid]
right_half = arr[mid:]
# loops split until each half is sorted
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
# combines the sorted halves to get the full sorted list
return merge(left_half, right_half)
def merge(left, right):
# empty list to store sorted elements
merged = []
# sets current index of each half to 0
i = j = 0
# compares the values in each half. If a value is lower than another value, the lower value is added to the merged list
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
# adds any remaining values from the halves to the merged list
while i < len(left):
merged.append(left[i])
i += 1
while j < len(right):
merged.append(right[j])
j += 1
return merged
# prints merge sorted lists
print(merge_sort(arr1))
print(merge_sort(arr2))
print(merge_sort(arr3))
print(merge_sort(arr4))
"""
* 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)