Sorting Algorithms Lesson
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)
- In order to sort this list, I would find the scan the list for the smallest number and place it on the left. I would keep scanning the list for the next smallest number until all of the numbers are sorted. = selection sorting algorithm
Explore
Get into groups of 3
We will be focusing on 4 algorithms today.
We will look at the first one together, Bubble Sort
image here (not linked for CI purposes)
What is happening with this sort?
- In this sort, pairs of values are being compared and switched if the right one is smaller. Although this algorithm requires multiple passes in order to guarantee the sorting is correct.
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.
- works by dividing an array into smaller subarrays, sorting each subarray, then merging the sorted subarrays back together.
- repeated until entire array is sorted
- time complexity of O(n log n)= can sort large arrays relatively quickly
- stable sort = the order of elements with equal values is preserved during the sort
- works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list
- The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it with the first element of the unsorted portion.
- After the N (size of the array) iteration, we will get a sorted array.
- Insertion sort is efficient for small data values
- works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part.
- Values from the unsorted part are picked and placed at the correct position in the sorted part.
- think left side of line is sorted and right side is not- keep moving line every time new number is sorted
- Time Complexity: O(N^2)
Practice
[75, 17, 46, 80, 67, 45, 69, 79, 40, 0]
How would you sort this list with...
- Bubble Sort
- Selection Sort
Bubble sort:First, 75 and 17 would be compared in which 17 would be placed in front. Then 75 and 46 would be compared, and 46 would be put in front. This process would continue until there are no more switches made. > Selection sort:First, the computer would search for the smallest value in the list, which is 0. Then, it would place it at the very left end. The computer will iterate through the list until the list is sorted. [88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort
- Insertion Sort
Merge Sort:I would split the list in half (5 values and 5 values) until it cannot be split anymore, and then sort each of the pieces. Once the pieces are sorted, they are added together, then sorted again. This process continues until the whole list is sorted.> Insertion Sort:I would start from the left, 88, and insert each value one by one into its ordered spot. The numbers on the left become the sorted portion and the numbers on the right are not sorted. I would keep moving down the line until the entire list is sorted.
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 merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
return merge(left_half, right_half)
def merge(left, right):
merged = []
left_index = 0
right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index].lower() < right[right_index].lower():
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
while left_index < len(left):
merged.append(left[left_index])
left_index += 1
while right_index < len(right):
merged.append(right[right_index])
right_index += 1
return merged
words = ['alphabetarian', 'automanual', 'casabe', 'Cyclophorus', 'Caph', 'crile', 'phonautographically', 'rattleran', 'redshirt', 'conformal']
sorted_words = merge_sort(words)
print("unsorted:")
print(words)
print("sorted:")
print(sorted_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: is efficeint for small data sets
- [Elephant, Banana, Cat, Dog, Apple]
- selection sort: will only take n size of array to sort (and can easily find next letter of alphebet)
- [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: can sort large data sets quickly 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? Lists and dictionaries in python are a non-primitive, a collection type, because they can only store one type of data at a time.
-
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 "pass-by-reference" since the actual list is changed into the sorted one. The original list is not preserved like with "pass-by-value".
-
- 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
import sys
numbers = [2,10,4,100,30,22]
# Traverse through all array elements
for i in range(len(numbers)):
# Find the minimum element in remaining
# unsorted array
min_idx = i
for j in range(i+1, len(numbers)):
if numbers[min_idx] > numbers[j]:
min_idx = j
# Swap the found minimum element with
# the first element
numbers[i], numbers[min_idx] = numbers[min_idx], numbers[i]
# Driver code to test above
print ("Sorted array")
for i in range(len(numbers)):
print("%d" %numbers[i],end=" , ")
"""
* 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)
"""
* 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_favs = [
{"name": "Dylan", "fav icecream": "chocolate"},
{"name": "Ava", "fav icecream": "vanilla"},
{"name": "Alexa", "fav icecream": "rocky road"},
]
# assuming uniform keys, pick 1st row as source of keys
key_row = List_favs[0]
# print list as defined
print("Original")
print(List_favs)
for key in key_row: # finds each key in the row
print(key)
bubbleSort(List_favs, key) # sort list of people
print(List_favs)
# Using merge sort
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
return merge(left_half, right_half)
def merge(left, right):
merged = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index]["name"] < right[right_index]["name"]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
merged.extend(left[left_index:])
merged.extend(right[right_index:])
return merged
List_favs = [
{"name": "Dylan", "fav icecream": "chocolate"},
{"name": "Ava", "fav icecream": "vanilla"},
{"name": "Alexa", "fav icecream": "rocky road"},
]
sorted_favs = merge_sort(List_favs)
print(sorted_favs)
# Using merge sort
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
return merge(left_half, right_half)
def merge(left, right):
merged = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index]["name"] < right[right_index]["name"]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
merged.extend(left[left_index:])
merged.extend(right[right_index:])
return merged
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"}
],
sorted_people = merge_sort(list_of_people)
print(sorted_people)