Sorting Algorithms
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
with bubble sort, you compare the two elements in the list at a time and swap the order if it is wrong, the same step is repeated to the next two elements in the list until the list is completely sorted. - Selection Sort
with selection sort, you repeatedly find the minimum element from the unsorted part of the list and swap it with the element at the beginning of the unsorted part.Explain.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort
with merge sort you divide the list into two until no longer divisible (creating a triangle), then you merge the elements back together in order from least to greatest until the full list is put back together (creating a diamond) - Insertion Sort
with insertion sort you compare elements in pairs. Starting with the first pair you compare, if they are in ascending order then you leave it as is and move on to the next pair to the right. However, if it is not in ascending order, then the pair is swapped. If, down the line, a number that is smaller than all the previous ones occur, then it will continue to get swapped until it is pushed up to the front.
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
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?
you should use merge sort when there are a lot of elements to sort through, bubble sort when you have a smaller dataset as it is easier to use, selection sort when memory space is constricted, and insertion sort when the dataset is already partially sorted. - Given the following lists...
- [0, 2, 6, 4, 8, 10]
for this data set I would use insertion because it isn;t a big dataset and is also very close to being sorted - [Elephant, Banana, Cat, Dog, Apple]
for this dataset I would use merge sort because it is more efficient due to its stability and time complexity - [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]
for this dataset I would use merge sort as well because it is a pretty big dataset. 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?
In Python, a list and a dictionary are considered collection types rather than primitive types. This is because they can hold multiple values or elements of different data types, making them more complex and versatile than primitive types. Lists are ordered collections that allow indexing and slicing operations, while dictionaries are unordered collections that store key-value pairs for efficient access to values. - Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
The list passed into the bubbleSort function is pass-by-reference. In Python, objects, including lists, are passed by reference when used as function arguments. When a list is passed as an argument to the bubbleSort function, it is passed by reference, meaning modifications made to the list within the function affect the original list outside. The bubbleSort function sorts the list in-place by swapping elements, and these modifications directly impact the original list. This demonstrates that the list is indeed passed by reference, allowing the function to modify the original list directly.
- 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)
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_of_food = [
{"name": "panini", "cost": "$10"},
{"name": "sushi", "cost": "12"},
{"name": "ramen", "cost": "15"},
{"name": "pizza", "cost": "$15"},
]
key_row = list_of_food[0]
print("Original")
print(list_of_food)
for key in key_row:
print(key)
bubbleSort(list_of_food, key)
print(list_of_food)
def insertionSort(lst, key):
for i in range(1, len(lst)):
current = lst[i]
j = i - 1
while j >= 0 and lst[j][key] > current[key]:
lst[j + 1] = lst[j]
j -= 1
lst[j + 1] = current
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"}
]
print("Original:")
for person in list_of_people:
print(person)
insertionSort(list_of_people, "age")
print("\nSorted by age:")
for person in list_of_people:
print(person)
Comparison: In the merge sort algorithm, comparisons are used to determine the relative order of elements during the merging process. The comparisons are performed based on a specified key or attribute of the elements being sorted.
Swaps: In the merge sort algorithm, swaps are not directly used to reorder elements. Instead, the merging process in merge sort involves creating new lists or arrays to store the sorted elements. The elements from the original list are selectively placed in the appropriate positions in the new merged list.
Time: Estimate of how the algorithm's performance scales with the input size. Merge sort has a time complexity of O(n log n), where n is the number of elements in the list. This means that as the list size doubles, the time taken to sort it will increase by a factor of approximately two times the logarithm of the list size.
Better way of printing data:
def mergeSort(arr, key):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = mergeSort(left, key)
right = mergeSort(right, key)
return merge(left, right, key)
def merge(left, right, key):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i][key] <= right[j][key]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
if __name__ == "__main__":
list_of_food = [
{"name": "panini", "cost": "$10"},
{"name": "sushi", "cost": "12"},
{"name": "ramen", "cost": "15"},
{"name": "pizza", "cost": "$15"},
]
key_row = list_of_food[0]
print("Original:")
for food in list_of_food:
print(food)
print("\nSorted by Name:")
sorted_list = mergeSort(list_of_food, "name")
for food in sorted_list:
print(food)
print("\nSorted by Cost:")
sorted_list = mergeSort(list_of_food, "cost")
for food in sorted_list:
print(food)