Sorting #

This lab introduces two sorting algorithms: Bubble Sort and Selection Sort.

Syllabus Topics [SL] #

• B2.4.3 Construct and trace algorithms to implement bubble sort and selection sort, evaluating their time and space complexities.

Key Vocabulary #

[0] Set up #

💻 Go into your unit folder and clone your repo. Be sure to replace yourGithubUsername with your actual username.

cd ~/desktop/dpcs/unit02_data_structures
git clone https://github.com/isf-dp-cs/lab_sorting_yourGithubUsername

cd lab_sorting_yourGithubUsername

💻 Enter the Poetry Shell to start the lab. As a reminder, we will run this command at the start of each lab, but only when we are inside a lab folder.

poetry shell

👾 💬 Exiting the poetry shell

When you want to exit the shell, you can type exit or ^D

[1] Bubble Sort #

What is Bubble Sort? #

📖 Here are the key steps in the Bubble Sort algorithm.

start at the beginning of the list
for each element in the list 
    compare the current element with the next element
    if the two values are not in order, 
        swap the elements
repeat until all elements have been sorted 

Code Bubble Sort #

💻 In bubble_sort.py, complete the function bubble_sort().

💻 Run your function using the test data at the bottom of the file.

📝 Practice Coding by Hand

1. Take out a piece of paper and write out entire the function for bubble_sort() without looking at your solution.

2. Double check your handwritten code against your typed code.

3. If you made mistakes, take note of them and fix your handwritten code.

4. Hand your written code it in to a teacher

[2] Selection Sort #

What is Selection Sort? #

📖 Here are the key steps in the Selection Sort algorithm.

at the start, the whole list is unsorted, so the **unsorted part** of the list starts at index 0
    loop through the **unsorted part** to find the smallest item 
    swap that smallest item with the first item in the **unsorted part**
update the start location of the **unsorted part** of the list
repeat until all elements have been sorted 

Code Selection Sort #

💻 In selection_sort.py, complete the function selection_sort().

💻 Run your function using the test data at the bottom of the file.

📝 Practice Coding by Hand

1. Take out a piece of paper and write out entire the function for selection_sort() without looking at your solution.

2. Double check your handwritten code against your typed code.

3. If you made mistakes, take note of them and fix your handwritten code.

4. Hand your written code it in to a teacher

[3] Parallel Lists: Sorting #

Currently your bubble_sort() and selection_sort() only sort one list. Let’s write new functions to ensure we can sort parallel lists using both sorting methods.

💻 In bubble_sort.py write bubble_sort_parallel(alist, blist) that takes two lists and sorts them using bubble sort.

💻 Test bubble_sort_parallel(alist, blist) using assert.

💻 In selection_sort.py write selection_sort_parallel(alist, blist) that takes two lists and sorts them using selection sort.

💻 Test selection_sort_parallel(alist, blist) using assert.

[4] Deliverables #

⚡✨ Once you complete the lab, be sure to complete these two steps:

📋 Update Syllabus Tracker: Go to your Syllabus Content Checklist in your Google Drive and update it accordingly.

💻 Push your work to Github

• git status
• git add -A
• git status
• git commit -m “describe your code here”
• git push
• remote

[5] Extension: Optimizing Bubble Sort #

Bubble sort already an inefficient algorithm, but your code is probably wasting even more time than it needs to.

Before you start optimizing, you want to be able to measure your progress as you improve your code.

💻 Edit your bubble_sort() to count how many times it has to compare the value of two numbers (in the if-statement). It should print this number out after it finishes.

💻 Put your edits to Github to track your progress.

Already sorted elements #

Check out this site with visualizations of bubble sort

Take a look at the first two “Unoptimized” visualizations. The red signifies numbers that are being compared. Even this “Unoptimized” algorithm is probably more efficient than your code. It doesn’t compare all the items every time. Which items does it ignore? Why?

💻 In bubble_sort.py write a new function efficient_bubble_sort() which ignores already-sorted elements like the “Unoptimized” visualization

💻 Run efficient_bubble_sort() and bubble_sort() and notice the difference in how many comparisons each algorithm makes

💻 Put your edits to Github to track your progress.

Retire the non-swaps #

Now look at the first optimization

Study up, and see if you can tell what it’s doing. The semisorted visualization may help you understand.

This optimization tracks when it has to swap/doesn’t swap, and if there are k non-swaps at the end, (k+1) elements can be retired (they don’t need to be compared any more).

💻 In bubble_sort.py write a new function optimized_bubble_sort() which ignores ALL already-sorted elements.

Make sure to test it out thoroughly to make sure it’s working. Use semi-sorted lists to showcase the changes you made.

💻 Run optimized_bubble_sort(), efficient_bubble_sort(), and bubble_sort() using the same semi-sorted starting list. Notice the difference in how many comparisons each algorithm makes

💻 Put your edits to Github to track your progress.