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 would compare the first to numbers to find the greater and put it ahead. Or just compare a number to the number before and swap if the second is greater than the other one.
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
Compare two numbers and move the lesser down, continue through entire list until everything is sorted. Example, switch 17 with 75, continue through list and repeat.
- Selection Sort
Compare two numbers and move the lesser down, but move sorted greater number to different section, only sort unsorted group, continue until all sorted. Example, switch 17 and 75, eventually when one portion is sorted, make a sorted section that remains untouched.
Explain.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort
Split list into two groups, sort, continue until groups sorted, rejoing groups. Split list between 58 and 43, repeat, sort, and then rejoin once sorted.
- Insertion Sort
Best if one element is out of place, compare out of place album with every element to find where it should be inserted. Compare 71 with every number in list to find correct position.
Explain.
import nltk
import random
nltk.download('words')
from nltk.corpus import words
english_words = words.words()
words = []
for i in range(10):
words.append(english_words[random.randint(0, len(english_words))])
sorted_words = sorted(words)
print("Random List:")
print(words)
print("Sorted List:")
print(sorted_words)
Discuss
Answer the following with your group.
- When should you use each algorithm? What makes an algorithm the right choice?
Insertion when only one element is out of place, selection when a small amount of elements needs to be sorted, and merge when there are many elements.
-
Given the following lists...
-
[0, 2, 6, 4, 8, 10]
Insertion, because only one element is out of place.
-
[Elephant, Banana, Cat, Dog, Apple]
Selection, moves sorted elements to a seperate group and sorts through unsorted elements only
-
[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, the large amount of elements means that merge would allow to a concert similar to parallel processing to speed up the process.
-
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? Collection because there are no classes and objects like there are in JavaScript.
-
Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
-
Pass by reference? The code uses the keys to each values, and not the value itself.
- 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
"""
* 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)
def selectionSort(array, size):
for ind in range(size):
min_index = ind
for j in range(ind + 1, size):
if array[j]["name"] < array[min_index]["name"]:
min_index = j
array[ind], array[min_index] = array[min_index], array[ind]
list_colleges = [
{"name": "UCLA", "city": "Los Angeles"},
{"name": "UCSB", "city": "Santa Barbara"},
{"name": "UCSD", "city": "San Diego"},
{"name": "UCI", "city": "Irvine"},
{"name": "UCD", "city": "Davis"},
{"name": "UCM", "city": "Merced"},
{"name": "UCR", "city": "Riverside"},
]
size = len(list_colleges)
selectionSort(list_colleges, size)
print('The list after sorting in alphabetical order by names:')
for college in list_colleges:
print(college)
def selectionSort(array, size): # defines type of sort
for ind in range(size):
min_index = ind
for j in range(ind + 1, size):
if array[j]["name"] < array[min_index]["name"]: # comparison is used here to determine which college is alphabetically earlier
min_index = j # this then swaps them, and redefines j so that the process and be done again
array[ind], array[min_index] = array[min_index], array[ind]
list_colleges = [ #list defined
{"name": "UCLA", "city": "Los Angeles"},
{"name": "UCSB", "city": "Santa Barbara"},
{"name": "UCSD", "city": "San Diego"},
{"name": "UCI", "city": "Irvine"},
{"name": "UCD", "city": "Davis"},
{"name": "UCM", "city": "Merced"},
{"name": "UCR", "city": "Riverside"},
]
size = len(list_colleges)
selectionSort(list_colleges, size)
print('The list after sorting in alphabetical order by names:')
for college in list_colleges:
print("Name:", college["name"])
print("City:", college["city"])
print()
"""
* 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_colleges = [
{"name": "UCLA", "city": "Los Angeles"},
{"name": "UCSB", "city": "Santa Barbara"},
{"name": "UCSD", "city": "San Diego"},
{"name": "UCI", "city": "Irvine"},
{"name": "UCD", "city": "Davis"},
{"name": "UCM", "city": "Merced"},
{"name": "UCR", "city": "Riverside"},
]
# assuming uniform keys, pick 1st row as source of keys
key_row = list_colleges[0]
# print list as defined
print("Original")
print(list_colleges)
for key in key_row: # finds each key in the row
print(key)
bubbleSort(list_colleges, key) # sort list of people
print(list_colleges)