Making progress! Here’s some miscellaneous tips and resources to help you through the next steps.
Thinking about algorithms
Sorting algorithms work by establishing some invariant and then gradually working through the data while maintaining that invariant until the invariant becomes equivalent to the statement “the list is fully sorted”.
As you’re writing your code, think carefully about what invariant the algorithm is trying to maintain. For each line in your program, ask yourself “what is this code doing?” and “are there under conditions under which this code could break my invariant?”. If the answer to the second question is yes, make sure that a) your answer to “what is this code doing?” fits your algorithm (and not a different one) and b) that your code guards against the condition that can break your invariant.
For selection sort, the invariant that you want to maintain is (hidden as spoiler - try to answer this for yourself, then click to reveal) that the entries to the left of write_index are in their fully sorted positions.
Every time you assign to the original list (arr[abc] = xyz), make sure that you can explain to yourself why the assignment is guaranteed to maintain the invariant (think about where abc and xyz are coming from, what had to be true to reach the current state, etc.). If the assignment isn’t guaranteed to maintain the invariant, you haven’t implemented the algorithm correctly.
Debugging
You have some code, and it’s not doing what you want it to do. This is a situation you’ll find yourself in for 90% of your programming career. This is a great time to invest in learning one of the more critical skills in programming: debugging.
Good debugging is huge topic (there’s entire books written on it!). Below are a few general strategies you can try out. You can find much for information about each one by searching online.
Go through your program line-by-line and explain (optionally to an inanimate of your choice) what each line is doing. This can help force you to think about your code from a different perspective, and make it apparent when what the code is supposed to do and what it actually does aren’t the same thing.
2. print logging
Add a bunch of print statements to your code. Focus on points where key state transitions occur. You don’t want to add too many, or the output will become unreadable. Good locations include beginning/end of functions, the beginning/end of loop bodies, the branches of an if/elif/else statement, etc.
Run your code. See how the state of your program evolved during execution and if it matches your expectations. Oftentimes there will be something very obviously suspicious. Focus on solving that one issue before moving on to the next. Rinse and repeat until the output is what you expected.
Here’s one of your attempts with some debugging print statements added, along with the corresponding output. You should notice a few things that seem off right away. For example, during the first iteration, the search_index never advances through the list.
sorting_by_selection with prints
def sorting_by_selection(arr):
print(f"initial array: {arr=}")
for write_index in range(0,len(arr)):
print(f"{write_index=}")
for search_index in range(write_index):
element1 = arr[search_index]
element2 = arr[search_index+1]
print(f" {search_index=} {element1=} {element2=}")
if element1 < element2:
min_index = element1
print(f" swapping entries at {min_index=} and {search_index=}")
arr[min_index], arr[search_index] = arr[search_index], arr[min_index]
print(f" array now {arr=}")
else:
continue
return arr
output
initial array: arr=[5, 3, 4, 1, 2]
write_index=0
write_index=1
search_index=0 element1=5 element2=3
write_index=2
search_index=0 element1=5 element2=3
search_index=1 element1=3 element2=4
swapping entries at min_index=3 and search_index=1
array now arr=[5, 1, 4, 3, 2]
write_index=3
search_index=0 element1=5 element2=1
search_index=1 element1=1 element2=4
swapping entries at min_index=1 and search_index=1
array now arr=[5, 1, 4, 3, 2]
search_index=2 element1=4 element2=3
write_index=4
search_index=0 element1=5 element2=1
search_index=1 element1=1 element2=4
swapping entries at min_index=1 and search_index=1
array now arr=[5, 1, 4, 3, 2]
search_index=2 element1=4 element2=3
search_index=3 element1=3 element2=2
3. Write reusable tests
Often times, in the course of debugging, you’ll fix one issue only to introduce a new one. A helpful way to catch that is by maintaining a suite of reusable tests that you can run every time you make changes to a piece of code.
Writing a representative test suite also has the secondary benefit of forcing you to think critically about the intended behavior of your code (e.g. exactly what combinations of inputs are allowable, what should happen for bad inputs, what relevant edge cases might exist…).
Some people even recommend writing a test suite before you even start writing the actual code (so-called test driven development).
For short scripts like this. it’s easy to your own ad-hoc test code. For example:
Example 1: Custom test runner
Code:
def sorting_by_selection(arr):
...
if __name__ == "__main__":
test_cases = [
[1, 2, 3, 4, 5], # sorted ascending
[5, 4, 3, 2, 1], # sorted descending
[5, 3, 4, 1, 2], # unsorted
[], # empty
[1], # single entry
[2, 1], # two entries
[1, 2, 1, 2, 1] # repeat entries
]
for case in test_cases:
expected = sorted(case)
actual = sorting_by_selection(case)
if actual != expected:
print(f"FAILURE: {case=} {expected=} {actual=}")
else:
print(f"OK: {case=}")
Output:
$ python3 ./sorting_by_selection_demo.py
FAILURE: case=[2, 1, 4, 3, 5] expected=[1, 2, 3, 4, 5] actual=[2, 1, 4, 3, 5]
FAILURE: case=[5, 4, 3, 2, 1] expected=[1, 2, 3, 4, 5] actual=[5, 4, 3, 2, 1]
FAILURE: case=[5, 1, 4, 3, 2] expected=[1, 2, 3, 4, 5] actual=[5, 1, 4, 3, 2]
OK: case=[]
OK: case=[1]
FAILURE: case=[2, 1] expected=[1, 2] actual=[2, 1]
FAILURE: case=[2, 1, 1, 2, 1] expected=[1, 1, 1, 2, 2] actual=[2, 1, 1, 2, 1]
For more complicated code with multiple independently testable units, it can be helpful to use a test framework. The standard library has doctest (demonstrated below) and unittest. There’s also 3rd party options like pytest. Personally, I use a combination of doctest and pytest in most of my projects.
Example 2: Using doctests
Code:
def sorting_by_selection(arr):
"""
>>> sorting_by_selection([1, 2, 3, 4, 5]) # sorted ascending
[1, 2, 3, 4, 5]
>>> sorting_by_selection([5, 4, 3, 2, 1]) # sorted descending
[1, 2, 3, 4, 5]
>>> sorting_by_selection([5, 3, 4, 1, 2]) # unsorted
[1, 2, 3, 4, 5]
>>> sorting_by_selection([]) # empty
[]
>>> sorting_by_selection([1]) # single entry
[1]
>>> sorting_by_selection([2, 1]) # two entries
[1, 2]
>>> sorting_by_selection([1, 2, 1, 2, 1]) # repeat entries
[1, 1, 1, 2, 2]
"""
...
if __name__ == "__main__":
import doctest
doctest.testmod()
Output:
$ python3 ./sorting_by_selection_demo.py
**********************************************************************
File "sorting_by_selection_demo.py", line 17, in __main__.sorting_by_selection
Failed example:
sorting_by_selection([1, 2, 3, 4, 5]) # sorted ascending
Expected:
[1, 2, 3, 4, 5]
Got:
[2, 1, 4, 3, 5]
**********************************************************************
File "sorting_by_selection_demo.py", line 19, in __main__.sorting_by_selection
Failed example:
sorting_by_selection([5, 4, 3, 2, 1]) # sorted descending
Expected:
[1, 2, 3, 4, 5]
Got:
[5, 4, 3, 2, 1]
**********************************************************************
File "sorting_by_selection_demo.py", line 21, in __main__.sorting_by_selection
Failed example:
sorting_by_selection([5, 3, 4, 1, 2]) # unsorted
Expected:
[1, 2, 3, 4, 5]
Got:
[5, 1, 4, 3, 2]
**********************************************************************
File "sorting_by_selection_demo.py", line 27, in __main__.sorting_by_selection
Failed example:
sorting_by_selection([2, 1]) # two entries
Expected:
[1, 2]
Got:
[2, 1]
**********************************************************************
File "sorting_by_selection_demo.py", line 29, in __main__.sorting_by_selection
Failed example:
sorting_by_selection([1, 2, 1, 2, 1]) # repeat entries
Expected:
[1, 1, 1, 2, 2]
Got:
[2, 1, 1, 2, 1]
**********************************************************************
1 items had failures:
5 of 7 in __main__.sorting_by_selection
***Test Failed*** 5 failures.
4. Use a debugger
Debuggers allow your to run your code line-by-line and see the exact state of every variable as your program executes. Typically, your IDE will have one already integrated. See the links below for more on what they can do and how to use one:
Specific Hints
Selection Sort Animation
Here’s an animation of how selection sort sorts a list. Note in particular how the relevant indices advance through the list and at what points swaps occur.
(Entries in pink denote the current minimum and search indices)
Hint 1
for search_index in range(write_index):
This iterates over the range [0, write_index), i.e. the left sorted sublist. You want the search index to iterate over the right unsorted sublist [write_index, end].
Hint 2
element1 = arr[i]
element2 = arr[i+1]
Think carefully about which elements need to be compared inside the inner loop. They generally won’t be adjacent elements, like in bubble sort.
