import random

numbers = []
for i in range(10):
    numbers.append(random.randint(0,100))
print("Random List")
print(numbers)
Random List
[83, 79, 50, 88, 16, 80, 9, 54, 35, 94]

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)

  • greatest to least
  • least to greatest
  • swap numbers for least to greatest

Explore

Get into groups of 3

We will be focusing on 4 algorithms today.

We will look at the first one together, Bubble Sort

bubble

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.

Merge

Selection

Insertion

Practice 1

[75, 17, 46, 80, 67, 45, 69, 79, 40, 0]

How would you sort this list with...

  • Bubble Sort

Bubble Sort works by repeatedly swapping adjacent elements if they are in the wrong order. It continues iterating through the list until the entire list is sorted.

Here's how the sorting process would unfold for the given list:

Pass 1: [17, 46, 75, 67, 45, 69, 79, 40, 0, 80]

Pass 2: [17, 46, 67, 45, 69, 75, 40, 0, 79, 80]

Pass 3: [17, 46, 45, 67, 69, 40, 0, 75, 79, 80]

Pass 4: [17, 45, 46, 67, 40, 0, 69, 75, 79, 80]

Pass 5: [17, 45, 46, 40, 0, 67, 69, 75, 79, 80]

Pass 6: [17, 45, 40, 0, 46, 67, 69, 75, 79, 80]

Pass 7: [17, 40, 0, 45, 46, 67, 69, 75, 79, 80]

Pass 8: [17, 0, 40, 45, 46, 67, 69, 75, 79, 80]

Pass 9: [0, 17, 40, 45, 46, 67, 69, 75, 79, 80]

After nine passes, the list is sorted in ascending order using Bubble Sort.

  • Selection Sort

Selection Sort works by repeatedly finding the minimum element from the unsorted part of the list and placing it at the beginning. It divides the list into two parts: sorted and unsorted. Here's how the sorting process would unfold for the given list:

Pass 1: [0, 17, 46, 80, 67, 45, 69, 79, 40, 75]

Pass 2: [0, 17, 40, 80, 67, 45, 69, 79, 46, 75]

Pass 3: [0, 17, 40, 45, 67, 80, 69, 79, 46, 75]

Pass 4: [0, 17, 40, 45, 46, 80, 69, 79, 67, 75]

Pass 5: [0, 17, 40, 45, 46, 67, 69, 79, 80, 75]

Pass 6: [0, 17, 40, 45, 46, 67, 69, 75, 80, 79]

Pass 7: [0, 17, 40, 45, 46, 67, 69, 75, 79, 80]

After seven passes, the list is sorted in ascending order using Selection Sort.

Practice 2

[88, 39, 53, 39, 58, 43, 74, 81, 71, 51]

How would you sort this list with...

  • Merge Sort

Merge Sort is a divide-and-conquer algorithm that recursively divides the list into smaller halves, sorts them individually, and then merges them back together to obtain the final sorted list. Here's how the sorting process would unfold for the given list:

Step 1: Divide the list into individual elements [88], [39], [53], [39], [58], [43], [74], [81], [71], [51]

Step 2: Merge the individual elements pairwise [39, 88], [39, 53], [39, 53, 88], [39, 39, 53, 53, 88], [43, 58], [43, 58, 74], [43, 58, 74, 81], [51, 71], [51, 71, 81], [51, 71, 74, 81]

Step 3: Merge the pairs until we obtain the final sorted list [39, 39, 53, 53, 58, 88], [43, 58, 74, 74, 81], [51, 71, 71, 81]

Final sorted list: [39, 39, 43, 51, 53, 53, 58, 71, 74, 74, 81, 81, 88]

  • Insertion Sort

Insertion Sort works by dividing the list into sorted and unsorted portions. It iterates over each element in the unsorted portion and inserts it into the correct position in the sorted portion.

Pass 1: [39, 88, 53, 39, 58, 43, 74, 81, 71, 51]

Pass 2: [39, 53, 88, 39, 58, 43, 74, 81, 71, 51]

Pass 3: [39, 39, 53, 88, 58, 43, 74, 81, 71, 51]

Pass 4: [39, 39, 53, 58, 88, 43, 74, 81, 71, 51]

Pass 5: [39, 39, 43, 53, 58, 88, 74, 81, 71, 51]

Pass 6: [39, 39, 43, 53, 58, 74, 88, 81, 71, 51]

Pass 7: [39, 39, 43, 53, 58, 74, 81, 88, 71, 51]

Pass 8: [39, 39, 43, 53, 58, 71, 74, 81, 88, 51]

Pass 9: [39, 39, 43, 53, 58, 71, 74, 81, 88, 51]

Pass 10: [39, 39, 43, 51, 53, 58, 71, 74, 81, 88]

Sorting Words

Sorting strings works in the same way as integers. Using your expertise algorithm, sort the following list of random words.

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)
Random List
['criniferous', 'logie', 'relatedness', 'prestidigital', 'Shirvan', 'ineducabilian', 'opiliaceous', 'undiscriminated', 'ballooner', 'treadmill']
[nltk_data] Downloading package words to
[nltk_data]     /Users/clairezhao/nltk_data...
[nltk_data]   Package words is already up-to-date!

Using Merge Sort

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].lower() < right[right_index].lower():
            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
words = ['criniferous', 'logie', 'relatedness', 'prestidigital', 'Shirvan', 'ineducabilian', 'opiliaceous', 'undiscriminated', 'ballooner', 'treadmill']
sorted_words = merge_sort(words)

print("unsorted:")
print(words)
print()
print("sorted:")
print(sorted_words)
unsorted:
['criniferous', 'logie', 'relatedness', 'prestidigital', 'Shirvan', 'ineducabilian', 'opiliaceous', 'undiscriminated', 'ballooner', 'treadmill']

sorted:
['ballooner', 'criniferous', 'ineducabilian', 'logie', 'opiliaceous', 'prestidigital', 'relatedness', 'Shirvan', 'treadmill', 'undiscriminated']

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]
    • [Elephant, Banana, Cat, Dog, Apple]
    • [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] 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?

      A list and dictionary are both considered collection types in python. Primitive types are integers, strings, booleans, and cannot hold and organize multiple values or objects.

    • 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. This means that the actual list object is being modified within the function, and any changes made to the list will be reflected outside the function as well.

  • 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": "taylor swift", "age": 33, "album": "folklore"},
    {"name": "harry styles", "age": 29, "album": "fine line"},
    {"name": "gracie abrams", "age": 23, "album": "good riddance"},
    ]
    
    # 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)
Original
[{'name': 'taylor swift', 'age': 33, 'album': 'folklore'}, {'name': 'harry styles', 'age': 29, 'album': 'fine line'}, {'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}]
name
[{'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}, {'name': 'harry styles', 'age': 29, 'album': 'fine line'}, {'name': 'taylor swift', 'age': 33, 'album': 'folklore'}]
age
[{'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}, {'name': 'harry styles', 'age': 29, 'album': 'fine line'}, {'name': 'taylor swift', 'age': 33, 'album': 'folklore'}]
album
[{'name': 'harry styles', 'age': 29, 'album': 'fine line'}, {'name': 'taylor swift', 'age': 33, 'album': 'folklore'}, {'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}]

Merge Sort

def mergeSort(arr, key):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    left = mergeSort(left, key)
    right = mergeSort(right, key)
    
    return merge(left, right, key)

def merge(left, right, key):
    merged = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        if left[i].get(key) <= right[j].get(key):
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    
    while i < len(left):
        merged.append(left[i])
        i += 1
    
    while j < len(right):
        merged.append(right[j])
        j += 1
    
    return merged


if __name__ == "__main__":
    # list/dictionary sample
    list_of_people = [
        {"name": "taylor swift", "age": 33, "album": "folklore"},
        {"name": "harry styles", "age": 29, "album": "fine line"},
        {"name": "gracie abrams", "age": 23, "album": "good riddance"},
    ]
    
    # assuming uniform keys, pick the first row as the source of keys
    key_row = list_of_people[0]

    # print the list as defined
    print("original")
    print(list_of_people)
    
    for key in key_row:  # find each key in the row
        print(key)
        sorted_list = mergeSort(list_of_people, key)  # sort the list of people
        print(sorted_list)
original
[{'name': 'taylor swift', 'age': 33, 'album': 'folklore'}, {'name': 'harry styles', 'age': 29, 'album': 'fine line'}, {'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}]
name
[{'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}, {'name': 'harry styles', 'age': 29, 'album': 'fine line'}, {'name': 'taylor swift', 'age': 33, 'album': 'folklore'}]
age
[{'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}, {'name': 'harry styles', 'age': 29, 'album': 'fine line'}, {'name': 'taylor swift', 'age': 33, 'album': 'folklore'}]
album
[{'name': 'harry styles', 'age': 29, 'album': 'fine line'}, {'name': 'taylor swift', 'age': 33, 'album': 'folklore'}, {'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}]

Comparison: In the merge sort algorithm, comparisons are used to determine the relative order of elements during the merging process. The comparisons are performed based on a specified key or attribute of the elements being sorted.

Swaps: In the merge sort algorithm, swaps are not directly used to reorder elements. Instead, the merging process in merge sort involves creating new lists or arrays to store the sorted elements. The elements from the original list are selectively placed in the appropriate positions in the new merged list.

Time: Estimate of how the algorithm's performance scales with the input size. Merge sort has a time complexity of O(n log n), where n is the number of elements in the list. This means that as the list size doubles, the time taken to sort it will increase by a factor of approximately two times the logarithm of the list size.

Better way of printing data:

def mergeSort(arr, key):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = mergeSort(left, key)
    right = mergeSort(right, key)

    return merge(left, right, key)

def merge(left, right, key):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i][key] <= right[j][key]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result

if __name__ == "__main__":
    list_of_people = [
        {"name": "taylor swift", "age": 33, "album": "folklore"},
        {"name": "harry styles", "age": 29, "album": "fine line"},
        {"name": "gracie abrams", "age": 23, "album": "good riddance"},
    ]

    key_row = list_of_people[0]

    print("Original:")
    for person in list_of_people:
        print(person)

    print("\nSorted by Name:")
    sorted_list = mergeSort(list_of_people, "name")
    for person in sorted_list:
        print(person)

    print("\nSorted by Age:")
    sorted_list = mergeSort(list_of_people, "age")
    for person in sorted_list:
        print(person)

    print("\nSorted by Album:")
    sorted_list = mergeSort(list_of_people, "album")
    for person in sorted_list:
        print(person)
Original:
{'name': 'taylor swift', 'age': 33, 'album': 'folklore'}
{'name': 'harry styles', 'age': 29, 'album': 'fine line'}
{'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}

Sorted by Name:
{'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}
{'name': 'harry styles', 'age': 29, 'album': 'fine line'}
{'name': 'taylor swift', 'age': 33, 'album': 'folklore'}

Sorted by Age:
{'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}
{'name': 'harry styles', 'age': 29, 'album': 'fine line'}
{'name': 'taylor swift', 'age': 33, 'album': 'folklore'}

Sorted by Album:
{'name': 'harry styles', 'age': 29, 'album': 'fine line'}
{'name': 'taylor swift', 'age': 33, 'album': 'folklore'}
{'name': 'gracie abrams', 'age': 23, 'album': 'good riddance'}