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)
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: You would compare each number with the number(s) next to it and flip their postion in the list based on the values of the number. This process would be repeated until the program successfully checks that it is sorted from least to greatest.
- Selection Sort: You would compare each number with the number after it and flip the greatest number to the later postion. You than check that number with the number after that and repeat the process. The process repeats the lenght of the list. The sorted list would start out at the last index.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort: You would split the numbers in to 2 groups for each group the lenght of the list divided by 2. You than sort each group while merging the groups together. This repeats until the list is the lenght of the starting list.
- Insertion Sort: You would compare each number with the number after it and flip the greatest number to the later postion. You than check that number with the number after that and repeat the process. The process repeats the lenght of the list. The sorted list would start out at the first index.
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?
All of the sorting methods work. However, the right algorithm is the one that completes the process in the least amount of time(time complexity).</p> </li>
Given the following lists...
-
[0, 2, 6, 4, 8, 10]
Bubble sorting would be the best because it only needs to flip 2 values, making the program finish in very few steps.
-
[Elephant, Banana, Cat, Dog, Apple]
Selection sorting would be the best because it sorts the word Elephant to the back very quick and apple is sent to the front early as the lenght of the list is decreasing.
-
[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 Sorting would be the best for this list because the time complextiy is short with it being O(n log n).
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 considered collection types because they are able to contain many data values and allow for code to easly access and manipulate the data.
-
Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
A list that is passed into a bubble sort is passed by reference because the output of the list would change if the list going into it was changed from the original list. <!-- - 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.
Comparison: The number of times a piece of data in the collection type is compared with another piece of data. This effects the time complexity of the sorting method.
Swaps: The number of times data in a collection type is rearranged in order to end up with the correct order. This effects the time complexity of the sorting method.
Time complextiy: The amount of time the sorting method with be expected to run in.
Use the code below to help guide your adventure
Bubble Sort Algorithm(Mr. Yueng's List)
""" * 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 for i in range(n): swapped = False for j in range(n-i): 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] if not swapped: return if __name__ == "__main__": starwarsmovies = [ {"name": "The Phantom Menace", "audience": 59, "rotten tomatoes": 51, "duration": 133, "money made(millions)": 431}, {"name": "Attack of the Clones", "audience": 56, "rotten tomatoes": 65, "duration": 143, "money made(millions)": 302}, {"name": "Revenge of the Sith", "audience": 66, "rotten tomatoes": 79, "duration": 140, "money made(millions)": 380}, {"name": "A New Hope", "audience": 96, "rotten tomatoes": 93, "duration": 121, "money made(millions)": 307}, {"name": "Empire Strikes Back", "audience": 97, "rotten tomatoes": 94, "duration": 124, "money made(millions)": 209}, {"name": "Return of the Jedi", "audience": 94, "rotten tomatoes": 83, "duration": 133, "money made(millions)": 252}, {"name": "The Force Awakens", "audience": 85, "rotten tomatoes": 93, "duration": 136, "money made(millions)": 936}, {"name": "The Last Jedi", "audience": 42, "rotten tomatoes": 91, "duration": 152, "money made(millions)": 620}, {"name": "The Rise of Skywalker", "audience": 86, "rotten tomatoes": 52, "duration": 142, "money made(millions)": 515} ] key_row = starwarsmovies[0].keys() for key in key_row: bubbleSort(starwarsmovies, key) print(key) print(starwarsmovies)
def selectionSort(lst, key): n = len(lst) for i in range(n-1): min_index = i for j in range(i+1, n): if lst[j].get(key, float('inf')) < lst[min_index].get(key, float('inf')): min_index = j if min_index != i: lst[i], lst[min_index] = lst[min_index], lst[i] if __name__ == "__main__": starwarsmovies = [ {"name": "The Phantom Menace", "audience": 59, "rotten tomatoes": 51, "duration": 133, "money made(millions)": 431}, {"name": "Attack of the Clones", "audience": 56, "rotten tomatoes": 65, "duration": 143, "money made(millions)": 302}, {"name": "Revenge of the Sith", "audience": 66, "rotten tomatoes": 79, "duration": 140, "money made(millions)": 380}, {"name": "A New Hope", "audience": 96, "rotten tomatoes": 93, "duration": 121, "money made(millions)": 307}, {"name": "Empire Strikes Back", "audience": 97, "rotten tomatoes": 94, "duration": 124, "money made(millions)": 209}, {"name": "Return of the Jedi", "audience": 94, "rotten tomatoes": 83, "duration": 133, "money made(millions)": 252}, {"name": "The Force Awakens", "audience": 85, "rotten tomatoes": 93, "duration": 136, "money made(millions)": 936}, {"name": "The Last Jedi", "audience": 42, "rotten tomatoes": 91, "duration": 152, "money made(millions)": 620}, {"name": "The Rise of Skywalker", "audience": 86, "rotten tomatoes": 52, "duration": 142, "money made(millions)": 515} ] key_row = starwarsmovies[0].keys() for key in key_row: selectionSort(starwarsmovies, key) print(key) print(starwarsmovies)
def selectionSort(list, key): n = len(list) for i in range(n-1): min_index = i for j in range(i+1, n): if list[j].get(key) < list[min_index].get(key): min_index = j if min_index != i: list[i], list[min_index] = list[min_index], list[i] 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] for key in key_row: selectionSort(list_of_people, key) print(key) print(list_of_people)
</div>def selectionSort(list, key): n = len(list) for i in range(n-1): min_index = i for j in range(i+1, n): if list[j].get(key) < list[min_index].get(key): min_index = j if min_index != i: list[i], list[min_index] = list[min_index], list[i] if __name__ == "__main__": starwarsmovies = [ {"name": "The Phantom Menace", "audience": 59, "rotten tomatoes": 51, "duration": 133, "money made(millions)": 431}, {"name": "Attack of the Clones", "audience": 56, "rotten tomatoes": 65, "duration": 143, "money made(millions)": 302}, {"name": "Revenge of the Sith", "audience": 66, "rotten tomatoes": 79, "duration": 140, "money made(millions)": 380}, {"name": "A New Hope", "audience": 96, "rotten tomatoes": 93, "duration": 121, "money made(millions)": 307}, {"name": "Empire Strikes Back", "audience": 97, "rotten tomatoes": 94, "duration": 124, "money made(millions)": 209}, {"name": "Return of the Jedi", "audience": 94, "rotten tomatoes": 83, "duration": 133, "money made(millions)": 252}, {"name": "The Force Awakens", "audience": 85, "rotten tomatoes": 93, "duration": 136, "money made(millions)": 936}, {"name": "The Last Jedi", "audience": 42, "rotten tomatoes": 91, "duration": 152, "money made(millions)": 620}, {"name": "The Rise of Skywalker", "audience": 86, "rotten tomatoes": 52, "duration": 142, "money made(millions)": 515} ] key_row = starwarsmovies[0].keys() for key in key_row: selectionSort(starwarsmovies, key) for movie in starwarsmovies: print(f"Name: {movie['name']}") print(f"Audience: {movie['audience']}") print(f"Rotten Tomatoes: {movie['rotten tomatoes']}") print(f"Duration: {movie['duration']}") print(f"Money Made (millions): {movie['money made(millions)']}") print()