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)
- Pair numbers. Select the larger number between each pair. The smaller number is set aside. The larger numbers form new pairs. Same procedure until only one number has emerged victorious. This is the largest number. This entire procedure is repeated until numbers are sorted from largest to smallest.
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?
Starting from left to right, numbers are compared in pairs and sorted.
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 75 and 17. Swap them. Compare 75 and 46. Swap them. Compare 75 and 80. Leave them as they are. Compare 80 and 67. Swap. 80 and 45. Swap. 80 and 69. Swap. 80 and 79. Swap. 80 and 40. Swap. 80 and 0. Swap: [17, 46, 75, 67, 45, 69, 79, 40, 0, 80]
Compare 17 and 46. Leave them. 46 and 75. Leave. 75 and 67. Swap. 75 and 45. Swap. 75 and 69. Swap. 75 and 79. Leave. 79 and 40. Swap. 79 and 0. Swap. 79 and 80. Leave: [17, 46, 75, 67, 45, 69, 75, 40, 0, 79, 80]
You get the idea.
- Selection Sort
Go through each item and put the smallest one at the beginning.
Explain.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort
Split into two groups.
[88, 39, 53, 39, 58] and [43, 74, 81, 71, 51]
[88, 39] and [53, 59,58] [43, 74] and [81, 71, 51]
[ 88] and [ 39] [53 ] and [59, 58] [43 ] and [73 ] [81, 71] and [ 51]
[39, 88] and [53, 58, 59] [43, 73] and [51, 71, 81]
[39, 53, 58, 59 88] and [43, 51, 71, 73, 81]
- Insertion
Start with [88].
Compare 39 with 88 insert it at the correct position:[39, 88]. Insert 53 at the correct position: [39, 53, 88].
Insert 39 at the correct position: [39, 39, 53, 88].
Insert 58 at the correct position: [39, 39, 53, 58, 88].
Insert 43 at the correct position: [39, 39, 43, 53, 58, 88].
Insert 74 at the correct position: [39, 39, 43, 53, 58, 74, 88].
Insert 81 at the correct position: [39, 39, 43, 53, 58, 74, 81, 88].
Insert 71 at the correct position: [39, 39, 43, 53, 58, 71, 74, 81, 88].
Insert 51 at the correct position: [39, 39, 43, 51, 53, 58, 71, 74, 81, 88].
Explain.
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
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left_half = merge_sort(lst[:mid])
right_half = merge_sort(lst[mid:])
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] <= right[right_index]:
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
words = []
for i in range(10):
words.append(english_words[random.randint(0, len(english_words))])
print("Random List:")
print(words)
sorted_words = merge_sort(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?
-
Depends on the type and size of the list. For instance, merge sorting is very good for large and complex lists.
-
Given the following lists...
-
[0, 2, 6, 4, 8, 10]
-
insertion
-
[Elephant, Banana, Cat, Dog, Apple]
-
Selection
-
[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
-
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 types, because collections are built-in data structures that can hold multiple values. Lists are ordered and mutable, while dictionaries are unordered and use key-value pairs for storage, making them suitable for various data manipulation tasks.
-
Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
Pass-by-reference, because any modifications made to the list inside the function will affect the original list outside the function. When the bubble sort algorithm swaps elements in the list, it directly modifies the original list, which is reflected in the 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
"""
* 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 mergeSort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = mergeSort(arr[:mid])
right_half = mergeSort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
merged = []
i = j = 0
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
merged.extend(left[i:])
merged.extend(right[j:])
return merged
if __name__ == "__main__":
numbers = [] # list here
# print original list
print("Original:")
print(numbers)
sorted_numbers = mergeSort(numbers)
# print sorted list
print("Sorted:")
print(sorted_numbers)
def mergeSort(list, key):
if len(list) <= 1:
return list
mid = len(list) // 2
left_half = list[:mid]
right_half = list[mid:]
# sort the left and right halves
left_half = mergeSort(left_half, key)
right_half = mergeSort(right_half, key)
return merge(left_half, right_half, key)
def merge(left, right, key):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i].get(key) <= right[j].get(key):
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
# add remaining elements from left and right halves
merged.extend(left[i:])
merged.extend(right[j:])
return merged
if __name__ == "__main__":
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"}
]
# pick the first row as the source of keys
key_row = list_of_people[0]
# print list
print("Original")
print(list_of_people)
for key in key_row: # find each key in the row
print(key)
sorted_list = mergeSort(list_of_people, key) # sort list
print(sorted_list)
def mergeSort(lst, key):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left_half = lst[:mid]
right_half = lst[mid:]
left_half = mergeSort(left_half, key)
right_half = mergeSort(right_half, key)
return merge(left_half, right_half, key)
def merge(left, right, key):
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i].get(key) <= right[j].get(key):
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged
if __name__ == "__main__":
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"}
]
key_row = list_of_people[0]
print("Original")
for person in list_of_people:
print(f"Name: {person['name']}, Age: {person['age']}, City: {person['city']}")
for key in key_row:
print("\nSorting by", key)
sorted_list = mergeSort(list_of_people, key)
for person in sorted_list:
print(f"Name: {person['name']}, Age: {person['age']}, City: {person['city']}")
Comparison
Time for bubble sort algorithm:
1) .1s
2) .1s
3) .1s
Time for merge sort algorithm:
1) .1s
2) .0s
3) .0s
I ran each algorithm three times and these were the results. In general, Merge Sort tends to have better time complexity than Bubble Sort. Merge Sort has a time complexity of O(n log n), while Bubble Sort has a time complexity of O(n^2), which is why the Merge Sort implementation runs faster than the Bubble Sort implementation, especially for larger input sizes. Merge Sort's efficiency comes from its divide-and-conquer approach and the merging step, which allows it to sort the list more efficiently.