Selection Sort Algorithm Not Working When Negative Number Is At Right End of Array

Question

I've seen a post earlier about someone saying the solution is to not swap outside the inner for loop. The algorithm below doesn't, but still doesn't work with list A only B

A = [4,2,7,-8,1,3,8,6,-1,-2]
B = [3,4,2,5,3,21,-7,3,26,-43,-12,22]

def selection_sort(list):
    
    for i in range(len(list)-1):
        smallest_index = i
        #print('i: ', list[i])
        for j in range(i+1,len(list)-1):
            if list[j] < list[smallest_index]:
                smallest_index = j
                #print('j: ', list[j])

        
        if smallest_index != i:
            list[i], list[smallest_index] = list[smallest_index], list[i]
                 
    
    return list

selection_sort(B)

Result for A

[-43, -12, -7, 2, 3, 3, 3, 4, 5, 21, 22, 26, -2]

BrokenBenchmark · Accepted Answer · 2022-03-05 19:55:11Z

1

The bounds on both your for loops are wrong; the upper bound on both loops should be len(list), not len(list) - 1. (Remember that the upper bound on range()s are exclusive.)

This correctly sorts the input:

B = [3,4,2,5,3,21,-7,3,26,-43,-12,22]

# Don't use list as a variable name; it shadows the list() builtin.
def selection_sort(input_list):
    for i in range(len(input_list)):
        smallest_index = i
        for j in range(i+1, len(input_list)):
            if input_list[j] < input_list[smallest_index]:
                smallest_index = j

        if smallest_index != i:
            input_list[i], input_list[smallest_index] = \
                input_list[smallest_index], input_list[i]
                 
    return input_list

print(selection_sort(B))

answered Mar 5, 2022 at 19:55

BrokenBenchmark

19.4k7 gold badges26 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Selection Sort Algorithm Not Working When Negative Number Is At Right End of Array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related