Sorting Algorithms
import random
numbers = []
for i in range(10):
numbers.append(random.randint(0,100))
print("Random List")
print(numbers)
Explore
Merge
- Splits, Sorts, then puts back together
Selection
- Finds the lowest value and puts it in the beginning of the array, and then goes to the next lowest value
Insertion
- Looks through the list and compares each value with the other values in the list and places the value where is should be compared to the entire list
Practice
[75, 17, 46, 80, 67, 45, 69, 79, 40, 0]
Bubble Sort
Looks at each value and moves it to the left or right depending on what its neighbor does
Selection Sort
Searches through all of the lists and finds the lowest, placing it at the very bottom, in this case the value would be 0, then 17, etc.
Merge Sort
We would split the value in half, in this case we would split it into 5 and 5, then each of those would be split into 2 and 3, then the 3 would be split into 2 and 1. All of these would then be sorted with lowest value at the bottom and then all put together again.
Insertion Sort
It will sort each value left to right like bubble sort but instead of just moving one value to the right, every value would be moved however far left it needs to be moved
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?
The best algorithm to choose depends on the smallest number of steps it takes to accomplish a task - Given the following lists...
- [0, 2, 6, 4, 8, 10]
Bubble sort would be the best option here since you only have to switch the 6 and 4
- [Elephant, Banana, Cat, Dog, Apple]
Selection sort would only takes 4 steps to accomplish
- [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 would be the best since it would split the table in half reducing the amount of times we would need to check the values against the other values
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?
Because they store numerous values and have a collection of values, lists and dictionaries are regarded as collection types in Python.
- Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
Because it relates to the list and modifies the list, it is pass-by-reference and related to 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
Is a list and/or dictionary in python considered a primitive or collection type? Why?
- Lists and Dictionarys are considered collection types because they are able to hold information and multiple different data values
Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
- It is pass-by-reference. Because it relates to the list and modifies the list, this has to do with output.
"""
* 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)
Hacks
- Create your own list
The list is created by our API sent byour project NIGHTHAWK-GUESSR Backend
- Create a list of dictionaries.
list = [ {"name": "Tom", "easy": 20, "medium": 50, "hard": 330}, {"name": "Zen", "easy": 60, "medium": 150, "hard": 930}, {"name": "Bob", "easy": 40, "medium": 56, "hard": 39}, {"name": "Ken", "easy": 50, "medium": 506, "hard": 239}, ]
- Use your expertise sorting algorithm
The sorting algorithm implemented link is Merge Sort. In our Project FE with Java Script I used Bubble Sort Algorithm to sort a list of dictionaries based off of "hard" game points key and displayed the sorted table. But here below I implemented in Merge Sort
- Analysis
Here is my analysis of the merge sort algorithm in terms of comparisons, swaps, and time:
Comparisons: The number of comparisons made by the merge sort algorithm is O(n log n), where n is the number of elements in the list. This is because the algorithm recursively divides the list in half, and each time it does so, it makes one comparison to determine which half is smaller.
Swaps: The number of swaps made by the merge sort algorithm is O(n), where n is the number of elements in the list. This is because the algorithm merges the sorted halves back together, and each time it does so, it may need to swap elements if the order of the elements in the two halves is different.
Time: The time complexity of the merge sort algorithm is O(n log n), where n is the number of elements in the list. This is because the algorithm recursively divides the list in half, and each time it does so, it takes O(n) time to sort the half.
I used merge sort here, the reason is merge sort algorithm is a stable sort, which means that the order of elements with equal values is preserved during the sort. Also, the merge sort algorithm is a efficient and effective sorting algorithm that is suitable for sorting large lists of data, but not for small data like our project.
- Here a better way to print the data, in a table of our project. The data is printed in a table with key and other elements https://github.com/NavanYatavelli/fastpages/issues/39
"""
THe list data used in this sorting is generated from our NIGHTHAWK-GUESSR Project.
This function implements the merge sort algorithm.
The algorithm works by recursively dividing the input list in half,
sorting each half, and then merging the sorted halves back together.
The merge() function is used to merge two sorted lists.
The merge_sort() function takes an input list and returns a sorted list.
"""
def merge_sort(list):
"""
This function recursively divides the input list in half,
sorts each half, and then merges the sorted halves back together.
Arguments: list: The input list.
Returns: A sorted list.
"""
# Base case: If the list is empty or has only one element, return it.
if len(list) <= 1:
return list
# Recursively divide the list in half.
middle = len(list) // 2
left = merge_sort(list[:middle])
right = merge_sort(list[middle:])
# Merge the sorted halves back together.
return merge(left, right)
def merge(left, right):
"""
This function merges two sorted lists.
Args:
left: The first sorted list.
right: The second sorted list.
Returns:
A sorted list that contains the elements of `left` and `right`.
"""
# Create a new list to store the merged elements.
result = []
# Iterate over the elements of left and right.
i, j = 0, 0
while i < len(left) and j < len(right):
# Compare the current elements of left and right.
# The element with the smaller hard value is added to the result list.
if left[i]["hard"] < right[j]["hard"]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Add any remaining elements from `left` to the result list.
result += left[i:]
# Add any remaining elements from `right` to the result list.
result += right[j:]
# Return the merged list.
return result
# Create a list of dictionaries.
list = [
{"name": "Tom", "easy": 20, "medium": 50, "hard": 330},
{"name": "Zen", "easy": 60, "medium": 150, "hard": 930},
{"name": "Bob", "easy": 40, "medium": 56, "hard": 39},
{"name": "Ken", "easy": 50, "medium": 506, "hard": 239},
]
print("Unsorted List from our NIGHTHAWK-GUESSR Project.")
# Print the sorted list.
print(list)
# Sort the list using the merge sort algorithm.
sorted_list = merge_sort(list)
print("Sorted List")
# Print the sorted list.
print(sorted_list)