Implement the Selection Sort Algorithm - Implement the Selection Sort Algorithm

Curriculum Help
1

Tell us what’s happening:

Hi there,
I stuck with passing test 6 regards avoiding unnecessary swapping. I don’t think my code does extra swapping but I may be wrong, any hints are appretiated?

Your code so far

def selection_sort(array):
    if len(array) <= 1:
        return array
    low = min(array)
    last_low_index = last_index = len(array) - 1 - array[::-1].index(low)
    #print(array, low, last_low_index)
    if last_low_index > 0:
        for index, el in enumerate(array):
            if el != low:
                if index == last_low_index + 1: 
                #all low elements are in front
                    #print(f"sorted in front: {index}, {el}")
                    array[index:] = selection_sort(array[index:])
                else:
                    array[last_low_index] = array[index]
                    array[index] = low
                    array[index+1:] = selection_sort(array[index+1:])
                break
    else: #already the min element in the front
        array[1:] =  selection_sort(array[1:])

    return array
        
#print(selection_sort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]))
#print(selection_sort([5643, 123, 123, 345, 234, 92]))
#print(selection_sort([5, 16, 99, 12, 567, 23, 15, 72, 3]))

Your browser information:

User Agent is: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/149.0.0.0 Safari/537.36

Challenge Information:

Implement the Selection Sort Algorithm - Implement the Selection Sort Algorithm

GitHub Link: https://github.com/freeCodeCamp/freeCodeCamp/blob/main/curriculum/challenges/english/blocks/lab-selection-sort/680b3ef395479b0e449ecb6e.md

2

Use some print statements within your function so you can see the sorting process unfold. This will give you some insight to how it’s working and if it’s doing extra swaps.

3

It begins by selecting the minimum value in the entire list and swapping it with the first element.

print(selection_sort([33, 1, 89, 2, 67, 245]))

I’ve just uncommented the existing print statements:

[33, 1, 89, 2, 67, 245] 1 1
[33, 89, 2, 67, 245] 2 2

I seems like the minimum value is 1 and the first element is 33 so it should swap 1 and 33 first?

Not sure how accurate these prints are since you are using recursion.

4

I think I did the most important prints, they are just commented out, but will look forward

5

I always replace the remaining (unsorted) part with the next inline recursion iteration at the end, the algorithm works fine, it has the expected outputs though. Maybe I should discard the recursive solution and try to solve it differently

6

Can you show or prove that 33 and 1 are the first elements to be swapped?

I think the recursion could be complicating things, and maybe does not work well with the tests.

7

if you put the line right after the inner else statement, it will print out the values to be swapped:
print(array[last_low_index], array[index])

8

If I print the array at the end of the inner else:

else:

                    array[last_low_index] = array[index]
                    array[index] = low
                    array[index+1:] = selection_sort(array[index+1:])
                    print(array)

I get this

[67, 89, 245]
[33, 67, 89, 245]
[2, 33, 67, 89, 245]
[1, 2, 33, 67, 89, 245]
[1, 2, 33, 67, 89, 245]

It depends when and where the tests are checking the array.

I could be wrong, but I think you should be able to print out the array after each swap and it should show something like

print(selection_sort([33, 1, 89, 2, 67, 245]))

[33, 1, 89, 2, 67, 245]
[1, 33, 89, 2, 67, 245]
[1, 2, 89, 33, 67, 245]

This is the only way to prove the swaps happen in the correct order.

9

I give this the solution just because the tip to output after each sequence lead me to debug it differently, although the real solution was to discard the recursive nature of the implementation (I think that is not expected, supported whatever)