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)
- Finding the lowest value and moving it to the front, then finding the next lowest value and moving it to the second position, and continue until the list is sorted.
- Finding the highest value and moving it to the end, then finding the next highest value and moving it to the second to last position, and continue until the list is sorted.
- Splitting the deck of cards into small groups, sort the groups, then merge the groups together. Do this 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?
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]
How would you sort this list with...
-
Bubble Sort: Find the nth value, then compare it to the n-1th value. If the nth value is less than the n-1th value, swap their positions. Do until the list is sorted.
1: [17, 75, 46, 80, 67, 45, 69, 79, 40, 0] 2: [17, 46, 75, 80, 67, 45, 69, 79, 40, 0] 3: [17, 46, 75, 67, 80, 45, 69, 79, 40, 0] 4: [17, 46, 75, 67, 45, 80, 69, 79, 40, 0] 5: [17, 46, 75, 67, 45, 69, 80, 79, 40, 0] 6: [17, 46, 75, 67, 45, 69, 79, 80, 40, 0] 7: [17, 46, 67, 75, 45, 69, 79, 80, 40, 0] 8: [17, 46, 67, 45, 75, 69, 79, 80, 40, 0] 9: [17, 46, 67, 45, 69, 75, 79, 80, 40, 0] 10: [17, 46, 67, 45, 69, 75, 79, 40, 80, 0] 11: [17, 46, 67, 45, 69, 75, 79, 40, 0, 80] 12: [17, 46, 45, 67, 69, 75, 79, 40, 0, 80] 13: [17, 46, 45, 67, 69, 75, 40, 79, 0, 80] 14: [17, 46, 45, 67, 69, 75, 40, 0, 79, 80] 15: [17, 45, 46, 67, 69, 75, 40, 0, 79, 80] 16: [17, 45, 46, 67, 69, 40, 75, 0, 79, 80] 17: [17, 45, 46, 67, 69, 40, 0, 75, 79, 80] 18: [17, 45, 46, 67, 40, 69, 0, 75, 79, 80] 19: [17, 45, 46, 67, 40, 0, 69, 75, 79, 80] 20: [17, 45, 46, 40, 67, 0, 69, 75, 79, 80] 21: [17, 45, 46, 40, 0, 67, 69, 75, 79, 80] 22: [17, 45, 40, 46, 0, 67, 69, 75, 79, 80] 23: [17, 45, 40, 0, 46, 67, 69, 75, 79, 80] 24: [17, 40, 45, 0, 46, 67, 69, 75, 79, 80] 25: [17, 40, 0, 45, 46, 67, 69, 75, 79, 80] 26: [17, 0, 40, 45, 46, 67, 69, 75, 79, 80] 27: [0, 17, 40, 45, 46, 67, 69, 75, 79, 80] -
Selection Sort: Find smallest value of an unsorted list, then it to its respective positions in a new list. Do until the list is sorted.
1: [0, 75, 17, 46, 80, 67, 45, 69, 79, 40] 2: [0, 17, 75, 46, 80, 67, 45, 69, 79, 40] 3: [0, 17, 40, 75, 46, 80, 67, 45, 69, 79] 3: [0, 17, 40, 45, 75, 46, 80, 67, 69, 79] 3: [0, 17, 40, 45, 46, 75, 80, 67, 69, 79] 3: [0, 17, 40, 45, 46, 67, 75, 80, 69, 79] 3: [0, 17, 40, 45, 46, 67, 69, 75, 80, 79] 3: [0, 17, 40, 45, 46, 67, 69, 75, 79, 80]
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
-
Merge Sort: Split the list into two halves, then split those halves into halves, and continue until each list is one item long. Then, merge the lists together, comparing the first item of each list and adding the smaller one to the new list. Do this until the list is sorted.
1: [88, 39, 53, 39, 58, 43, 74, 81, 71, 51] 2: [88, 39, 53, 39, 58] [43, 74, 81, 71, 51] 3: [88, 39] [53, 39, 58] [43, 74] [81, 71, 51] 4: [88] [39] [53] [39] [58] [43] [74] [81] [71] [51] 5: [39, 88] [39, 53] [39, 58] [43, 74] [71, 81] [51] 6: [39, 39, 53, 58, 88] [43, 74, 71, 81] [51] 7: [39, 39, 43, 53, 58, 71, 74, 81, 88] [51] 8: [39, 39, 43, 51, 53, 58, 71, 74, 81, 88] -
Insertion Sort: Take the nth value, then compare it to the n-1th value. if the nth value is less than the n-1th value, swap the items. If they can't be swapped again, move on to the next pair of values. If they can, keep swapping until the nth value is in the correct position. Do until the list is sorted.
1: [88, 39, 53, 39, 58, 43, 74, 81, 71, 51] 2: [39, 88, 53, 39, 58, 43, 74, 81, 71, 51] 3: [39, 53, 88, 39, 58, 43, 74, 81, 71, 51] 4: [39, 53, 39, 88, 58, 43, 74, 81, 71, 51] 5: [39, 39, 53, 88, 58, 43, 74, 81, 71, 51] 6: [39, 39, 53, 58, 88, 43, 74, 81, 71, 51] 7: [39, 39, 43, 53, 58, 88, 74, 81, 71, 51] 8: [39, 39, 43, 53, 58, 74, 88, 81, 71, 51] 9: [39, 39, 43, 53, 58, 74, 81, 88, 71, 51] 10: [39, 39, 43, 53, 58, 71, 74, 81, 88, 51] 11: [39, 39, 43, 53, 58, 71, 74, 81, 51, 88] 12: [39, 39, 43, 53, 58, 71, 74, 51, 81, 88] 13: [39, 39, 43, 53, 58, 71, 51, 74, 81, 88] 14: [39, 39, 43, 53, 58, 51, 71, 74, 81, 88] 15: [39, 39, 43, 53, 51, 58, 71, 74, 81, 88] 16: [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] - Bubble Sort: Only one is out of order, so it only requires one step.
- [Elephant, Banana, Cat, Dog, Apple] - Selection Sort: This would take only 4 iterations, while everything else takes more than four.
- [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: Runs in the least amount of time given a large input
Large inputs -> Merge Small changes -> Bubble or Insertion Large changes -> Selection
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?
- 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, 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
def merge_sort(list):
if len(list)>1:
mid = len(list)//2
right=list[mid:]
left=list[:mid]
merge_sort(right)
merge_sort(left)
i = j = k = 0 # not really sure what this is doing # edit: i sets index of right list, j sets index of left list, k sets index of origional list
while i < len(right) and j < len(left):
if left[j] <= right[i]:
list[k] = left[j] # if the first index of the left list is smaller, set the first value of the list to the smallest value (first index) of the left list
j += 1 # move on to test the next value, and see if we can replace the first value of the origional list with a smaller value
else:
list[k] = right[i] # else, add the smallest value to the original list (first index of right list)
i += 1 # move on to test the next value, and see if we can replace the first value of the origional list with a smaller value
k += 1 # move on to (replacing) the next index of the origional list # note: this effectively splits the list again into halves of smaller and larger values
# these check to see if any values are left in either list, and if so continue going through the list and adding them to the origional list (because these values are already sorted)
while i < len(right):
list[k] = right[i]
i += 1
k += 1
while j < len(left):
list[k] = left[j]
j += 1
k += 1
return list
sorted = merge_sort([0,4,3,1,3,2,1,2,3,4])
print(sorted)
"""
* Creator: Nighthawk Coding Society
Bubble Sort of a List with optimizations
"""
def merge_sort(list):
if len(list)>1:
mid = len(list)//2
right=list[mid:]
left=list[:mid]
merge_sort(right)
merge_sort(left,)
i = j = k = 0 # not really sure what this is doing # edit: i sets index of right list, j sets index of left list, k sets index of origional list
while i < len(right) and j < len(left):
if left[j] <= right[i]:
list[k] = ""
list[k] = left[j] # if the first index of the left list is smaller, set the first value of the list to the smallest value (first index) of the left list
j += 1 # move on to test the next value, and see if we can replace the first value of the origional list with a smaller value
else:
list[k] = ""
list[k] = right[i] # else, add the smallest value to the original list (first index of right list)
i += 1 # move on to test the next value, and see if we can replace the first value of the origional list with a smaller value
k += 1 # move on to (replacing) the next index of the origional list # note: this effectively splits the list again into halves of smaller and larger values
# these check to see if any values are left in either list, and if so continue going through the list and adding them to the origional list (because these values are already sorted)
while i < len(right):
list[k] = right[i]
i += 1
k += 1
while j < len(left):
list[k] = left[j]
j += 1
k += 1
return list
def printList(arr):
for i in range(len(arr)):
print(arr[i], end=" ")
print()
# Driver Code
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
print("Given array is", end="\n")
printList(arr)
#mergeSort(arr)
print("Sorted array is: ", end="\n")
printList(arr)
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)
print(len(list_of_people))
for key in key_row: # finds each key in the row
unsorted=[]
print(key)
for i in range(0, len(list_of_people)-1):
unsorted.append(list_of_people[i][key])
print(f"unsorted list: {unsorted}")
sorted = merge_sort(unsorted) # sort list of people
print(f"sorted list {sorted}")
i+=1