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 two numbers at a time in the list, and the larger is already on the right it moves on, and if it on the left, it swaps places with the other number it was compared to.
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.
- Merge sort is basically sub-sorting. It divides the list into multiple smaller lists, then sorts each of the smaller lists. Then, it reassembles the sections into the original list, but now it is sorted. Advantages of merge sort is that it is time-efficient and it is a stable sort.
- Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.
- The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Practice
[75, 17, 46, 80, 67, 45, 69, 79, 40, 0]
How would you sort this list with...
- Bubble Sort: First, take the first two numbers, 75 and 17, and since 75 is greater than 17, it swaps places with the 17. Then, it compares 75 and 46 as the second and third numbers of the list, and it is swapped again. Once it goes next to the 80, it does not get swapped this time because 75 is smaller than 80. It continues this check and swap method through the whole list.
- Selection Sort: To sort the list [75, 17, 46, 80, 67, 45, 69, 79, 40, 0] using Selection Sort, we start by finding the minimum element (0) and swapping it with the first element (75). Then, we find the minimum element from the remaining unsorted part and swap it with the second element (17). This process continues until the entire list is sorted. The final sorted list is [0, 17, 40, 45, 46, 67, 69, 75, 79, 80].
Explain.
[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]
How would you sort this list with...
- Merge Sort:To sort the list [88, 39, 53, 39, 58, 43, 74, 81, 71, 51] using Merge Sort, we follow a divide-and-conquer approach. First, we recursively divide the list into smaller sublists until each sublist contains only one element. Then, we merge these sublists in a sorted manner. To merge two sublists, we compare the elements from each sublist and place them in the correct order. We continue this process until all the sublists are merged into a single sorted list. Applying Merge Sort to the given list, the final sorted list is [39, 39, 43, 51, 53, 58, 71, 74, 81, 88].- Insertion Sort: Insertion Sort is a simple sorting algorithm that works by iteratively building a sorted portion of the list. Starting with the second element, it compares each element with the ones before it and inserts it at the correct position by shifting elements to the right. This process is repeated for each subsequent element until the entire list is sorted. When applying Insertion Sort to the list [88, 39, 53, 39, 58, 43, 74, 81, 71, 51], the final sorted list is [39, 39, 43, 51, 53, 58, 71, 74, 81, 88].
Explain.
import nltk
import random
nltk.download('words')
from nltk.corpus import words
english_words = words.words()
word_list = []
for i in range(10):
word_list.append(english_words[random.randint(0, len(english_words))])
print("Random List:")
print(word_list)
# Sort the list in alphabetical order
word_list.sort(key=str.lower)
print("Sorted List (Alphabetical Order):")
print(word_list)
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]
- Merge sort is the best choice due to its efficient performance.
- [Elephant, Banana, Cat, Dog, Apple]:
- Merge sort can be used, although sorting algorithms are typically designed for numerical values.
- [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 is the recommended algorithm for efficient sorting. 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?
- In Python, both lists and dictionaries are considered collection types. A list is an ordered collection of elements, while a dictionary is an unordered collection of key-value pairs. They are not considered primitive types because they can contain multiple values and have built-in methods for manipulation and retrieval.
- Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.
- In Python, the list passed into the bubble sort function behaves as a pass-by-reference. When you pass a list to a function, a reference to the original list is created, and any modifications made to the list within the function affect the original list. The output reflects this behavior because the changes made inside the bubble sort function are visible outside of it.
- 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 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)
# Example list
my_list = [5, 2, 8, 1, 9, 3]
# Your sorting algorithm implementation (e.g., selection sort)
def selectionSort(lst):
n = len(lst)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if lst[j]["age"] < lst[min_index]["age"]: # Compare based on "age" key
min_index = j
lst[i], lst[min_index] = lst[min_index], lst[i]
# Testing your algorithm with my bubble sort
print("Original List (my_list):")
print(my_list)
bubbleSort(list_of_people, "age") # Sorting based on the "age" key
# Sorting using bubble sort from the provided code
print("Sorted List (bubble sort):")
print(my_list)
# Testing my list with your sorting algorithm
print("Original List (list_of_people):")
print(list_of_people)
selectionSort(list_of_people) # Sorting using your selection sort algorithm
print("Sorted List (selection sort):")
print(list_of_people)