Sorting Algorithm Hacks
My expert algorithm was the selection sort
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)
- Bubble sort checks if the next element is less than the pointed element, and swaps the elements if true, which sorts the list from least to greatest
- Bogosort randomizes the list until it is sorted.
- Selection sort selects a number and moves all higher numbers to the end of the list, sorted from least to greatest.
Practice
[75, 17, 46, 80, 67, 45, 69, 79, 40, 0]
How would you sort this list with...
- Bubble Sort
- Selection Sort
Explain.
With bubble sort, I see that 17 is less than 75, so I swap 17 and 75. Onto the second element, I see that 46 is less than 75, so I swap 46 and 75. Onto the third element, 80 is greater than 75, stay. 67 is less than 80, swap. 45 is less than 80, swap. 69 is less than 80, swap. 79 is less than 80, swap. 40 is less than 80, swap. 0 is less than 80, swap. Go through the algorithm again, because it is not completely sorted.
With selection sort, I treat 75 as the minimum. 17 is less than the minimum, so insert 17 as the new first element, the new minimum. Go through until I find 0, the new minimum. Then go through the algorithm until we sort the list fully.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort
- Insertion Sort
Explain.
With insertion sort, it is the same logic as bubble sort, but instead of two elements being inspected at a time, it will be the whole list, which can be thought of as more efficient in some use cases.
With merge sort, we will split the list into [88, 39, 53, 39, 58] and [43, 74, 81, 71, 51]. Split those two down until we have multiple lists with a maximum of two elements, Then in those lists, we sort the numbers, and merge all the sorted lists from least to greatest.
Discuss
Answer the following with your group.
- When should you use each algorithm? What makes an algorithm the right choice?
If we treat the letters in alphabetical order as numbers, the difficulty is about the same, depending on what algorithm we use.
- Given the following lists...
- [0, 2, 6, 4, 8, 10]
- [Elephant, Banana, Cat, Dog, Apple]
- [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] Select the algorithm you believe is best for each, explain.
The first and second lists can be of any sorting algorithm since they are small enough to not matter with time complexity. However, while selection, insertion and bubble sorting have a time complexity of O(n^2), merge sort has a complexity of O(logn), making merge sort the best algorithm for the third list.
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?
- A list and a dictionary are considered collection types rather than primitive types. Primitive types in Python include fundamental data types such as integers, floating-point numbers, booleans, and strings. These types are indivisible and have a fixed size in memory. They are not built from other types but are considered atomic values.
- Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to
output.
- In Python, when a list is passed as an argument to the bubble sort algorithm, it is actually passed by reference, which means it behaves as a "pass-by-reference" scenario. This is because objects in Python, including lists, are mutable, and their references are passed to functions rather than creating a copy of the entire object.
- 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 of Dictionaries with optimizations, every key in row 0 is used to sort and resort list.
"""
# 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 selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j][0] < arr[min_index][0]:
min_index = j
if min_index != i:
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
def print_data(arr):
for item in arr:
print(f"Key: {item[0]}, Other Elements: {item[1:]}")
data = [(3, 'c', 'd', 'e'), (2, 'a', 'b', 'c'), (1, 'x', 'y', 'z'), (4, 'm', 'n', 'o')]
sorted_data = selection_sort(data)
print_data(sorted_data)
In the code above, the selection_sort function sorts the input array arr using the selection sort algorithm. The array is sorted based on the first element of each item (the key) using comparisons and swaps. The print_data function is used to print the sorted data in a readable format. It iterates over each item in the array and prints the key first, followed by the other elements. You can modify the print statement as per your requirements. In the example usage, we have an input array data containing tuples, each with a key and other elements. The selection_sort function is called to sort the data, and then the sorted data is printed using the print_data function. This shows how my algorithm uses the created list to use selection sort (my expertise sorting algorithm) tested against my sort, and how it uses comparisons, swaps, and the O(n^2) time complexity, as well as printing the data, key, and elements in a viewable form.