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?
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
-
Selection Sort
Explain.
- Bubble:I would sort this list with bubble sort by iterating through the list multiple times. Each time, I would go to the right and look at 2 consecutive elements - for example, 75 and 17. If the one on the right is smaller than the one on the left, I will switch the two, so here, I switch 75 and 17 since 17 is smaller than 75. I keep doing this until the list is sorted.- Selection: This sort would be used to sort this list by starting at index 0 and going through the whole list and taking the minimum value and then switching it with index 0. This then happens again with index 1, 2, 3, etc until the list is complete with values low to high. Iterate through the list and replace 0 with 75, then start at index 1 (number 17) and do the same but since 17 is the smallest, nothing changes. Then start at index 2 and iterate through, repeating this process until the list is ordered low to high.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort
- Insertion Sort
Explain.
- Merge:I will split the list until only individual elements remain - 88, 39, 53, 39, 58, 43, 74, 81, 71, 51. The elements are sorted and then merged into 1 sorted list.- Insertion:The process will be very similar to Bubble Sort except insertion will only iterate through the list once. It looks at 2 consecutive elements and switches them if the one on the right is smaller - 75 and 17. It also looks at the new consecutive elements after switching so that the whole list is sorted. For example, after switching 75 and 17, 75 is also bigger than 46 so the two are switched.
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)
def new_words():
# You can now use the 'english_words' list in your code
random_words = []
for i in range(10):
random_words.append(english_words[random.randint(0,len(english_words))])
return random_words
print("Random List")
print(new_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, you only have to swap the 4 and 6
- [Elephant, Banana, Cat, Dog, Apple]
- Selection sort, it only needs to go through it and swap apple with elephant, it will essentially be completed on the first run
- [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, this is a very large list and using bubble or selection will have to run through it a lot of times. Merge sorting is simpler. Select the algorithm you believe is best for each, explain.
- [0, 2, 6, 4, 8, 10]
def insertion_sort(word_list):
for i in range(1, len(word_list)):
current_word = word_list[i]
j = i - 1
while j >= 0 and word_list[j] > current_word:
word_list[j + 1] = word_list[j]
j -= 1
word_list[j + 1] = current_word
random_words = new_words()
print("Random List:")
print(random_words)
insertion_sort(random_words)
print("Sorted List:")
print(random_words)
def bubbleSort(word_list):
x = len(word_list)
for i in range(x - 1):
swapped = False
for j in range(x - i - 1):
if word_list[j] > word_list[j + 1]:
word_list[j], word_list[j + 1] = word_list[j + 1], word_list[j]
swapped = True
if not swapped:
break
words = new_words()
print(words)
bubbleSort(words)
print("Sorted List:")
print(words)
def selectionSort(word_list):
n = len(word_list)
for i in range(n):
smallI = i
smallV = word_list[i]
for j in range(i + 1, n):
if word_list[j] < smallV:
smallI = j
smallV = word_list[j]
word_list[i], word_list[smallI] = word_list[smallI], word_list[i]
words = new_words()
print(words)
selectionSort(words)
print("Sorted List:")
print(words)
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?
- Traditionally, a list/dictionary is considered a non-primitive type and therefore, a collection. This is because a collection type is something that stores and organizes multiple values which is what lists and dictionaries do.
- Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
- 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)
My List:
grades = [
{"name": "Dillon", "percent": 99, "letter": "A"},
{"name": "Steven", "percent": 83, "letter": "B"},
{"name": "Noor", "percent": 77, "letter": "C"},
{"name": "Lucas", "percent": 68, "letter": "D"}
]
Test your list with my bubble sort
"""
* 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
grades = [
{"name": "Dillon", "percent": 99, "letter": "A"},
{"name": "Steven", "percent": 83, "letter": "B"},
{"name": "Noor", "percent": 77, "letter": "C"},
{"name": "Lucas", "percent": 68, "letter": "D"}
]
# assuming uniform keys, pick 1st row as source of keys
key_row = grades[0]
# print list as defined
print("Original")
print(grades)
for key in key_row: # finds each key in the row
print(key)
bubbleSort(grades, key) # sort list of people
print(grades)
Test my list with your new sort (Selection)
def selectionSort(array, size):
for index in range(size):
min_index = index
for j in range(index + 1, size):
if array[j] < array[min_index]:
min_index = j
(array[index], array[min_index]) = (array[min_index], array[index])
arr = [-2, 45, 0, 11, -9,88,-97,-202,747]
size = len(arr)
selectionSort(arr, size)
print(arr)
def selectionSort(array, size, key): # add parameter for what key to sort in dictionary
for index in range(size):
min_index = index
for j in range(index + 1, size):
if array[j][key] < array[min_index][key]:
min_index = j
array[index], array[min_index] = array[min_index], array[index]
arr = [
{"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"}
]
size = len(arr)
selectionSort(arr, size, "age")
print("By age:" + str(arr))
selectionSort(arr, size, "name")
print("By name:" + str(arr))
selectionSort(arr, size, "city")
print("By city:" + str(arr))