Sorting
Several 2D arrays and Animations hacks are provided to further learn iteration and data in Python. The objective is to build a stronger foundation in iteration and data. Also, it is important to see concepts like printing color and moving objects in terminal, prior to moving to frontend development with JavaScript.
import random
numbers = []
for i in range(10):
numbers.append(random.randint(0,100))
print("Random List")
print(numbers)
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)
- You could search for the smallest number, move that to the front, then repeat with the next smallest and the next, until all the numbers have been moved.
- You could also just keep moving them around randomly and check, repeat until in order.
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 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 Compare 75 and 17, 17 is smaller, so they swap, continue on until you get to the largest number and moves it to the end.
- Selection Sort
Compare 75 and 17, 17 is smaller, so they swap, continue on until you get to the largest number and moves it to the end.
Explain.
I would do selection as bubble sort would take a while to move each individual element. Using selection should be faster by moving each piece.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort Split into equal groups of 2, then remerges them in which they are sorted.
- Insertion Sort
Look for the smallest number, 39, and move it to the front, then repeat with next smallest number until it is sorted.
Explain.
I would use insertion as merge sort would take longer to split into different sub groups.
To sort the words, I would look to see which letter comes first, then move
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]
- Selection sorting as you only need to move one element within the array.
- [Elephant, Banana, Cat, Dog, Apple]
- Selection as you just swap the first and last element.
- [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 as it is a large list so the time complexity of merge sort woul be useful here. Select the algorithm you believe is best for each, explain.
"""
* 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)
arr = [5, 1, 421, 43, 532,54,6,3,2,1,431,321,54,6,8,4,3,543,43,2]
def mergeSort(arr):
if len(arr) > 1:
# Finding the mid of the array
mid = len(arr)//2
# Dividing the array elements
L = arr[:mid]
# into 2 halves
R = arr[mid:]
# Sorting the first half
mergeSort(L)
# Sorting the second half
mergeSort(R)
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
# Code to print the list
def printList(arr):
for i in range(len(arr)):
print(arr[i], end=" ")
print()
# Driver Code
if __name__ == '__main__':
print("Given array is", end="\n")
printList(arr)
mergeSort(arr)
print("Sorted array is: ", end="\n")
printList(arr)
# This code is contributed by Mayank Khanna
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 are both considered to be collection types. Primitive types are like setting x=10, but dictionaries and lists store more complex values making them collection types.
- Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output. Passed by reference because the reference values are used within the function. For example, when we sort a list using pass-by-reference, if we display the results outside the function, it remains sorted. But if we used pass-by-pass, outside of te function, it would not be sorted.
- 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
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
left_half = merge_sort(left_half)
right_half = merge_sort(right_half)
return merge(left_half, right_half)
def merge(left, right):
merged = []
left_index = 0
right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
while left_index < len(left):
merged.append(left[left_index])
left_index += 1
while right_index < len(right):
merged.append(right[right_index])
right_index += 1
return merged
arr = [5, 1, 421, 43, 532, 54, 6, 3, 2, 1, 431, 321, 54, 6, 8, 4, 3, 543, 43, 2]
sorted_arr = merge_sort(arr)
print(sorted_arr)
def merge_sort_racers(racers, key):
if len(racers) <= 1:
return racers
mid = len(racers) // 2
left_half = racers[:mid]
right_half = racers[mid:]
left_half = merge_sort_racers(left_half, key)
right_half = merge_sort_racers(right_half, key)
return merge_racers(left_half, right_half, key)
def merge_racers(left, right, key):
merged = []
left_index = 0
right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index][key] < right[right_index][key]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
while left_index < len(left):
merged.append(left[left_index])
left_index += 1
while right_index < len(right):
merged.append(right[right_index])
right_index += 1
return merged
list_of_racers = [
{"name": "Nathan", "car": "BMW 228i", "top_speed": "135"},
{"name": "Azeem", "car": "Nissan Leaf", "top_speed": "308"},
{"name": "Arteen", "car": "Audi A4", "top_speed": "150"},
]
# Sort by name
sorted_racers_name = merge_sort_racers(list_of_racers, "name")
print("Sorted by name:")
for racer in sorted_racers_name:
print(f"Name: {racer['name']}, Car: {racer['car']}, Top Speed: {racer['top_speed']}")
# Sort by car
sorted_racers_car = merge_sort_racers(list_of_racers, "car")
print("\nSorted by car:")
for racer in sorted_racers_car:
print(f"Name: {racer['name']}, Car: {racer['car']}, Top Speed: {racer['top_speed']}")
# Sort by top speed
sorted_racers_speed = merge_sort_racers(list_of_racers, "top_speed")
print("\nSorted by top speed:")
for racer in sorted_racers_speed:
print(f"Name: {racer['name']}, Car: {racer['car']}, Top Speed: {racer['top_speed']}")