import random

numbers = []
for i in range(10):
    numbers.append(random.randint(0,100))
print("Random List")
print(numbers)
Random List
[9, 62, 78, 54, 18, 74, 58, 84, 20, 46]

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)

  • Checking each number in the list to see if it is less than or greater than and gradually alter the list until it is sorted.

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 (Geek for Geeks linked below) 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

    Bubble sort will compare the first and second value and move the least one to the end and continue this pattern over and over again.

  • Selection Sort

    Selection sort will look at the values and sort them into the following.

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

How would you sort this list with...

  • Merge Sort

    Merge sort will continually splitting the lists in half and merging them in a manner where it is sorted and it will continue this pattern until it is done.

  • Insertion Sort

    Insertion Sort will take the first number and look at al the values then place it in the correct place and this procedure will repeat with all the numbers.

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)
236736
Random List
['prosneusis', 'perichondritis', 'nitrobarite', 'countercraft', 'wrongness', 'cosmorganic', 'explicable', 'comparativeness', 'sparge', 'unaccounted']
[nltk_data] Downloading package words to /home/haeryny/nltk_data...
[nltk_data]   Package words is already up-to-date!

Popcorn Hacks

words = new_words()
print(words)
def bubbleSort(list):
    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]
            keyN1 = list[j+1]
            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
        
bubbleSort(words)
print(words)
words = new_words()
print(words)
def selectionSort(list):
    n = len(list)  # length is n
    
    # List is traversed from index 0 to n-1, n elements
    for i in range(n):
        smallI = i  # small index is captured
        smallV = list[i]

        # Inner traversal looks at elements after i
        for j in range(i+1, n):
            # Save reference if less
            keyV = list[j]
            if keyV < smallV:
                smallI = j  # small index is replaced
                smallV = keyV
        
        # swap smallest to current i positon, sorting left to right
        list[i], list[smallI] = list[smallI], list[i]  # single line swap 
        
selectionSort(words)
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, you compare two values at a time because only two numbers have to be switched.
    • [Elephant, Banana, Cat, Dog, Apple]
      • Selection, you compare one value with all the other values and all the words have to be reversed in the list.
    • [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, you can view large groups of value at a time.

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?

      In Python, a list and a dictionary are considered collection types rather than primitive types. Primitive types in Python are basic and immutable data types, such as integers, floating-point numbers, booleans, and strings. They are not capable of storing multiple values or elements. On the other hand, a list is an ordered collection of elements, allowing duplicate values and supporting various operations like indexing, appending, removing, and iterating. It is mutable, which means you can modify its elements after creation. A dictionary, also known as a hash table or associative array, is an unordered collection of key-value pairs. Each value is associated with a unique key, allowing efficient lookup and retrieval of values based on the keys. Dictionaries are also mutable. Both lists and dictionaries provide a way to organize and manipulate data in a more complex manner than primitive types, making them collection types in Python.

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

      Python uses a mechanism called "pass-by-object-reference," which means that when you pass a variable as an argument to a function, a reference to the object is passed, rather than creating a new copy of the object. This behavior applies to mutable objects like lists. When a list is passed by reference to the bubble sort algorithm, any modifications made to the list within the function will be reflected in the original list outside the function. Bubble sort works by swapping elements within the list, and these swaps will directly affect the original list.

  • 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)
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'}]

My Own List and Merge Sort

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

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

    left_half = mergeSort(left_half)
    right_half = mergeSort(right_half)

    return merge(left_half, right_half)

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

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            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__":
    # my own list
    list_of_artists = [
    {"name": "Bob Ross", "age": 895, "country": "Italy"},
    {"name": "Leonardo Da Vinci", "age": 653, "country": "America"},
    {"name": "Van Gogh", "age": 485, "country": "France"},
    {"name": "Picasso", "age": 212, "country": "Rome"}
    ]
    
    key_row = list_of_artists[0]

    
    # print list as defined
    print("Original")
    print(list_of_artists)

    print("Bubble Sort")
    for key in key_row:  # finds each key in the row
        print(key)
        bubbleSort(list_of_artists, key)  # sort list of people
        print(list_of_artists)

    print("Merge Sort")
    for key in key_row:  # finds each key in the row
        print(key)
        mergeSort(list_of_artists, key)  # sort list of people
        print(list_of_artists)

  
Original
[{'name': 'Bob Ross', 'age': 895, 'country': 'Italy'}, {'name': 'Leonardo Da Vinci', 'age': 653, 'country': 'America'}, {'name': 'Van Gogh', 'age': 485, 'country': 'France'}, {'name': 'Picasso', 'age': 212, 'country': 'Rome'}]
Bubble Sort
name
[{'name': 'Bob Ross', 'age': 895, 'country': 'Italy'}, {'name': 'Leonardo Da Vinci', 'age': 653, 'country': 'America'}, {'name': 'Picasso', 'age': 212, 'country': 'Rome'}, {'name': 'Van Gogh', 'age': 485, 'country': 'France'}]
age
[{'name': 'Picasso', 'age': 212, 'country': 'Rome'}, {'name': 'Van Gogh', 'age': 485, 'country': 'France'}, {'name': 'Leonardo Da Vinci', 'age': 653, 'country': 'America'}, {'name': 'Bob Ross', 'age': 895, 'country': 'Italy'}]
country
[{'name': 'Leonardo Da Vinci', 'age': 653, 'country': 'America'}, {'name': 'Van Gogh', 'age': 485, 'country': 'France'}, {'name': 'Bob Ross', 'age': 895, 'country': 'Italy'}, {'name': 'Picasso', 'age': 212, 'country': 'Rome'}]
Merge Sort
name
[{'name': 'Bob Ross', 'age': 895, 'country': 'Italy'}, {'name': 'Leonardo Da Vinci', 'age': 653, 'country': 'America'}, {'name': 'Picasso', 'age': 212, 'country': 'Rome'}, {'name': 'Van Gogh', 'age': 485, 'country': 'France'}]
age
[{'name': 'Picasso', 'age': 212, 'country': 'Rome'}, {'name': 'Van Gogh', 'age': 485, 'country': 'France'}, {'name': 'Leonardo Da Vinci', 'age': 653, 'country': 'America'}, {'name': 'Bob Ross', 'age': 895, 'country': 'Italy'}]
country
[{'name': 'Leonardo Da Vinci', 'age': 653, 'country': 'America'}, {'name': 'Van Gogh', 'age': 485, 'country': 'France'}, {'name': 'Bob Ross', 'age': 895, 'country': 'Italy'}, {'name': 'Picasso', 'age': 212, 'country': 'Rome'}]

Merge Sort on Class Example

print("Original")
print(list_of_people)
    
for key in key_row:  # finds each key in the row
        print(key)
        mergeSort(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'}]

Is a list and/or dictionary in Python considered a primitive or collection type? Why? A list in Python is considered a collection type. It is an ordered and changeable collection of elements that can be of different data types. As a collection type, lists offer more functionality and flexibility compared to primitive types like integers or booleans.

Is the list passed into bubble sort "pass-by-value" or "pass-by-reference"? Describe why in relation to output. When a list is passed into bubble sort in Python, it is passed by reference. Python follows a "pass-by-object-reference" mechanism for parameter passing. This means that instead of creating a copy of the list, a reference to the original list is passed to the function.

list = [2,6,7,3]
print(list)
def bubble_sort(arr):
    n = len(arr)   # sets n to value of length of array
    for i in range(n): # iterate through all vaues
        for j in range(0, n-i-1):  # compare adjacent values
            if arr[j] > arr[j+1]: # if previous element is greater than the one after 
                arr[j], arr[j+1] = arr[j+1], arr[j] # then swap them
                # this loop is done for whole list
    return arr
bubble_sort(list)
[2, 6, 7, 3]
[2, 3, 6, 7]
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 = []
for person in list_of_people:
    key_row.append(person["age"])
print(key_row)

bubble_sort(key_row)
[18, 63, 18, 21]
[18, 18, 21, 63]