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)

  • I would figure out where the smallest number is located and move it to the front. Then disregard that number and repeat the process until the list 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

bubble-sort

What is happening with this sort?

It compares consecutive elements and sorts in a linear fashion.

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]

Would you sort this list with...

  • Bubble Sort
  • Selection Sort

    Selection sort because it would be faster since the 0 and 75 would swap, making it closer to being sorted quicker.

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

Would you sort this list with...

  • Merge Sort
  • Insertion Sort

    Insertion because it has a faster time complexity than if merge sort was used.

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)
[nltk_data] Downloading package words to /home/azeemk/nltk_data...
[nltk_data]   Unzipping corpora/words.zip.
Random List
['zinco', 'spendible', 'mesodermal', 'consequentialness', 'unidealist', 'blepharophryplasty', 'autotypic', 'Heracleidan', 'spike', 'haruspices']

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 sort because you would only move one thing.

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

      Selection sort because it would only take one pass

    • [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 because it's a long list. 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 a dictionary are considered collection types rather than primitive types. They are implemented using more complex data structures and algorithms than the primitive types. For example, a list in Python is typically implemented as a dynamic array, while a dictionary is usually implemented using a hash table. These data structures and algorithms are more complex than those used to implement primitive types, which is why they are considered collection types.

    • 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, not by value. When a variable is passed as an argument to a function, a reference to the object is passed, not a copy of the object itself.

  • 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

# Selection sort with basic arrays

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

arr1 = [5, 3, 1, 6, 4, 2]
arr2 = ["banana", "apple", "orange", "pear", "kiwi", "grape"]
arr3 = [10, 5, 20, 2, 4, 6, 8, 1, 9, 3]
arr4 = ["dog", "cat", "bird", "hamster", "fish", "turtle"]

print(selection_sort(arr1))
print(selection_sort(arr2))
print(selection_sort(arr3))
print(selection_sort(arr4))
[1, 2, 3, 4, 5, 6]
['apple', 'banana', 'grape', 'kiwi', 'orange', 'pear']
[1, 2, 3, 4, 5, 6, 8, 9, 10, 20]
['bird', 'cat', 'dog', 'fish', 'hamster', 'turtle']
# Selection sort with list of dictionaries and sorting by key

def selectionSort(lst, key):
    n = len(lst)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if lst[j][key] < lst[min_idx][key]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]
    return lst

def prettyPrint(lst, key):
    sorted_list = selectionSort(lst, key)
    print("Sorted by", key + ":")
    for person in sorted_list:
        print("\tName:", person['name'])
        print("\tAge:", person['age'])
        print("\tCity:", person['city'])
        print("")

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]

for key in key_row:
    prettyPrint(list_of_people, key)
Sorted 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

Sorted 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

Sorted 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

"""
* 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("Sorted by " + 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'}]
Sorted 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'}]
Sorted 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'}]
Sorted 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'}]