import random

numbers = []
for i in range(10):
    numbers.append(random.randint(0,100))
print("Random List")
print(numbers)
Random List
[70, 88, 8, 54, 95, 47, 71, 90, 20, 36]

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)

  • Pair numbers. Select the larger number between each pair. The smaller number is set aside. The larger numbers form new pairs. Same procedure until only one number has emerged victorious. This is the largest number. This entire procedure is repeated until numbers are sorted from largest to smallest.

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?

Starting from left to right, numbers are compared in pairs and sorted.

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.

Merge

Selection

Insertion

Practice

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

How would you sort this list with...

  • Bubble Sort

Compare 75 and 17. Swap them. Compare 75 and 46. Swap them. Compare 75 and 80. Leave them as they are. Compare 80 and 67. Swap. 80 and 45. Swap. 80 and 69. Swap. 80 and 79. Swap. 80 and 40. Swap. 80 and 0. Swap: [17, 46, 75, 67, 45, 69, 79, 40, 0, 80]

Compare 17 and 46. Leave them. 46 and 75. Leave. 75 and 67. Swap. 75 and 45. Swap. 75 and 69. Swap. 75 and 79. Leave. 79 and 40. Swap. 79 and 0. Swap. 79 and 80. Leave: [17, 46, 75, 67, 45, 69, 75, 40, 0, 79, 80]

You get the idea.

  • Selection Sort

Go through each item and put the smallest one at the beginning.

Explain.

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

How would you sort this list with...

  • Merge Sort

Split into two groups.

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

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

[ 88] and [ 39] [53 ] and [59, 58] [43 ] and [73 ] [81, 71] and [ 51]

[39, 88] and [53, 58, 59] [43, 73] and [51, 71, 81]

[39, 53, 58, 59 88] and [43, 51, 71, 73, 81]

  • Insertion

Start with [88].

Compare 39 with 88 insert it at the correct position:[39, 88]. Insert 53 at the correct position: [39, 53, 88].

Insert 39 at the correct position: [39, 39, 53, 88].

Insert 58 at the correct position: [39, 39, 53, 58, 88].

Insert 43 at the correct position: [39, 39, 43, 53, 58, 88].

Insert 74 at the correct position: [39, 39, 43, 53, 58, 74, 88].

Insert 81 at the correct position: [39, 39, 43, 53, 58, 74, 81, 88].

Insert 71 at the correct position: [39, 39, 43, 53, 58, 71, 74, 81, 88].

Insert 51 at the correct position: [39, 39, 43, 51, 53, 58, 71, 74, 81, 88].

Explain.

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

def merge_sort(lst):
    if len(lst) <= 1:
        return lst

    mid = len(lst) // 2
    left_half = merge_sort(lst[:mid])
    right_half = merge_sort(lst[mid:])

    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

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged

words = []
for i in range(10):
    words.append(english_words[random.randint(0, len(english_words))])

print("Random List:")
print(words)

sorted_words = merge_sort(words)

print("Sorted List:")
print(sorted_words)
Random List:
['plowwright', 'Macareus', 'pusslike', 'dicker', 'aumery', 'meute', 'cylindered', 'accersitor', 'disprivilege', 'Acanthia']
Sorted List:
['Acanthia', 'Macareus', 'accersitor', 'aumery', 'cylindered', 'dicker', 'disprivilege', 'meute', 'plowwright', 'pusslike']
[nltk_data] Downloading package words to /home/manimani/nltk_data...
[nltk_data]   Package words is already up-to-date!

Discuss

Answer the following with your group.

  • When should you use each algorithm? What makes an algorithm the right choice?

  • Depends on the type and size of the list. For instance, merge sorting is very good for large and complex lists.

  • Given the following lists...

    • [0, 2, 6, 4, 8, 10]

    • insertion

    • [Elephant, Banana, Cat, Dog, Apple]

    • Selection

    • [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

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?

      Collection types, because collections are built-in data structures that can hold multiple values. Lists are ordered and mutable, while dictionaries are unordered and use key-value pairs for storage, making them suitable for various data manipulation tasks.

    • Is the list passed into bubble sort "pass-by-value" or "pass-by-reference? Describe why in relation to output.

      Pass-by-reference, because any modifications made to the list inside the function will affect the original list outside the function. When the bubble sort algorithm swaps elements in the list, it directly modifies the original list, which is reflected in the output.

  • 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

"""
* 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)
Original
[{'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'}]
name
[{'name': 'John', 'age': 63, 'city': 'Eugene'}, {'name': 'Risa', 'age': 18, 'city': 'New York'}, {'name': 'Ryan', 'age': 21, 'city': 'Los Angeles'}, {'name': 'Shekar', 'age': 18, 'city': 'San Francisco'}]
age
[{'name': 'Risa', 'age': 18, 'city': 'New York'}, {'name': 'Shekar', 'age': 18, 'city': 'San Francisco'}, {'name': 'Ryan', 'age': 21, 'city': 'Los Angeles'}, {'name': 'John', 'age': 63, 'city': 'Eugene'}]
city
[{'name': 'John', 'age': 63, 'city': 'Eugene'}, {'name': 'Ryan', 'age': 21, 'city': 'Los Angeles'}, {'name': 'Risa', 'age': 18, 'city': 'New York'}, {'name': 'Shekar', 'age': 18, 'city': 'San Francisco'}]

Merge Sort

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

    mid = len(arr) // 2
    left_half = mergeSort(arr[:mid])
    right_half = mergeSort(arr[mid:])

    return merge(left_half, right_half)


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

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

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

    return merged


if __name__ == "__main__":
    numbers = [] # list here

    # print original list
    print("Original:")
    print(numbers)

    sorted_numbers = mergeSort(numbers)
    
    # print sorted list
    print("Sorted:")
    print(sorted_numbers)
Original:
[8, 3, 1, 7, 0, 4, 2, 5, 9, 6]
Sorted:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Replacing Bubble Sort with Merge Sort

def mergeSort(list, key):
    if len(list) <= 1:
        return list
    
    mid = len(list) // 2
    left_half = list[:mid]
    right_half = list[mid:]
    
    # sort the left and right halves
    left_half = mergeSort(left_half, key)
    right_half = mergeSort(right_half, key)
    
    return merge(left_half, right_half, 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
    
    # add remaining elements from left and right halves
    merged.extend(left[i:])
    merged.extend(right[j:])
    
    return merged

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"}
    ]
    
    # pick the first row as the source of keys
    key_row = list_of_people[0]

    # print list
    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 list
        print(sorted_list)
Original
[{'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'}]
name
[{'name': 'John', 'age': 63, 'city': 'Eugene'}, {'name': 'Risa', 'age': 18, 'city': 'New York'}, {'name': 'Ryan', 'age': 21, 'city': 'Los Angeles'}, {'name': 'Shekar', 'age': 18, 'city': 'San Francisco'}]
age
[{'name': 'Risa', 'age': 18, 'city': 'New York'}, {'name': 'Shekar', 'age': 18, 'city': 'San Francisco'}, {'name': 'Ryan', 'age': 21, 'city': 'Los Angeles'}, {'name': 'John', 'age': 63, 'city': 'Eugene'}]
city
[{'name': 'John', 'age': 63, 'city': 'Eugene'}, {'name': 'Ryan', 'age': 21, 'city': 'Los Angeles'}, {'name': 'Risa', 'age': 18, 'city': 'New York'}, {'name': 'Shekar', 'age': 18, 'city': 'San Francisco'}]

Formatted

def mergeSort(lst, key):
    if len(lst) <= 1:
        return lst
    
    mid = len(lst) // 2
    left_half = lst[:mid]
    right_half = lst[mid:]
    
    left_half = mergeSort(left_half, key)
    right_half = mergeSort(right_half, key)
    
    return merge(left_half, right_half, 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
    
    merged.extend(left[i:])
    merged.extend(right[j:])
    
    return merged

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]

    print("Original")
    for person in list_of_people:
        print(f"Name: {person['name']}, Age: {person['age']}, City: {person['city']}")
    
    for key in key_row:
        print("\nSorting by", key)
        sorted_list = mergeSort(list_of_people, key)
        for person in sorted_list:
            print(f"Name: {person['name']}, Age: {person['age']}, City: {person['city']}")
Original
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

Sorting by name
Name: John, Age: 63, City: Eugene
Name: Risa, Age: 18, City: New York
Name: Ryan, Age: 21, City: Los Angeles
Name: Shekar, Age: 18, City: San Francisco

Sorting by age
Name: Risa, Age: 18, City: New York
Name: Shekar, Age: 18, City: San Francisco
Name: Ryan, Age: 21, City: Los Angeles
Name: John, Age: 63, City: Eugene

Sorting by city
Name: John, Age: 63, City: Eugene
Name: Ryan, Age: 21, City: Los Angeles
Name: Risa, Age: 18, City: New York
Name: Shekar, Age: 18, City: San Francisco

Comparison

Time for bubble sort algorithm:

1) .1s

2) .1s

3) .1s

Time for merge sort algorithm:

1) .1s

2) .0s

3) .0s

I ran each algorithm three times and these were the results. In general, Merge Sort tends to have better time complexity than Bubble Sort. Merge Sort has a time complexity of O(n log n), while Bubble Sort has a time complexity of O(n^2), which is why the Merge Sort implementation runs faster than the Bubble Sort implementation, especially for larger input sizes. Merge Sort's efficiency comes from its divide-and-conquer approach and the merging step, which allows it to sort the list more efficiently.