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?
It compares consecutive elements and sorts in a linear fashion.
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]
Would you sort this list with...
- Bubble Sort
-
Selection Sort
Selection sort because it would be faster since the 0 and 75 would swap, making it closer to being sorted quicker.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
Would you sort this list with...
- Merge Sort
-
Insertion Sort
Insertion because it has a faster time complexity than if merge sort was used.
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?
- Given the following lists...
- [0, 2, 6, 4, 8, 10]
Insertion sort because you would only move one thing.
- [Elephant, Banana, Cat, Dog, Apple]
Selection sort because it would only take one pass
- [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 sort because it's a long list. 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?
A list and a dictionary are considered collection types rather than primitive types. They are implemented using more complex data structures and algorithms than the primitive types. For example, a list in Python is typically implemented as a dynamic array, while a dictionary is usually implemented using a hash table. These data structures and algorithms are more complex than those used to implement primitive types, which is why they are considered collection types.
- Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
The list passed into bubble sort is passed by reference, not by value. When a variable is passed as an argument to a function, a reference to the object is passed, not a copy of the object itself.
- 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, 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
# Selection sort with basic arrays
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
arr1 = [5, 3, 1, 6, 4, 2]
arr2 = ["banana", "apple", "orange", "pear", "kiwi", "grape"]
arr3 = [10, 5, 20, 2, 4, 6, 8, 1, 9, 3]
arr4 = ["dog", "cat", "bird", "hamster", "fish", "turtle"]
print(selection_sort(arr1))
print(selection_sort(arr2))
print(selection_sort(arr3))
print(selection_sort(arr4))
# Selection sort with list of dictionaries and sorting by key
def selectionSort(lst, key):
n = len(lst)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if lst[j][key] < lst[min_idx][key]:
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
return lst
def prettyPrint(lst, key):
sorted_list = selectionSort(lst, key)
print("Sorted by", key + ":")
for person in sorted_list:
print("\tName:", person['name'])
print("\tAge:", person['age'])
print("\tCity:", person['city'])
print("")
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:
prettyPrint(list_of_people, key)
"""
* 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("Sorted by " + key)
bubbleSort(list_of_people, key) # sort list of people
print(list_of_people)