Indexes out of range in selection sort algorithm

Question

Regarding Selection Sort Algorithm. Let's assume that my array has 10 elements. If I leave len() and remove the -1 in the loop that belongs to the selection_sort() function I get that in the last iteration that i will be equal to 9. So we pass that value to the select() function and it is gonna start with j=10, and there is no such a thing. The program should rise an error since there is no such thing as if array[9] > array[10], array[10] does not exist, instead, the program shows the array sorted. Why doesn't the program rise an error?

def select(array, start):
    minIndex = start

    for j in range(start + 1, len(array)):
        if array[minIndex] > array[j]:
            minIndex = j

def selection_sort(array):
    
   # If I put len(array) removing the -1, I get it sort it anyway
    for i in range(len(array) - 1 ): # Here, I do not get it
        minIndex = select(array, i)
        tmp = array[i]
        array[i] = array[minIndex]
        array[minIndex] = tmp

Output:

Unsorted array: [9, 7, 3, 10, 2, 6, 4, 5, 8, 1]

Iteration i =  0
Iteration j =  1
Iteration j =  2
Iteration j =  3
Iteration j =  4
Iteration j =  5
Iteration j =  6
Iteration j =  7
Iteration j =  8
Iteration j =  9
[1, 7, 3, 10, 2, 6, 4, 5, 8, 9]
Iteration i =  1
Iteration j =  2
Iteration j =  3
Iteration j =  4
Iteration j =  5
Iteration j =  6
Iteration j =  7
Iteration j =  8
Iteration j =  9
[1, 2, 3, 10, 7, 6, 4, 5, 8, 9]
Iteration i =  2
Iteration j =  3
Iteration j =  4
Iteration j =  5
Iteration j =  6
Iteration j =  7
Iteration j =  8
Iteration j =  9
[1, 2, 3, 10, 7, 6, 4, 5, 8, 9]
Iteration i =  3
Iteration j =  4
Iteration j =  5
Iteration j =  6
Iteration j =  7
Iteration j =  8
Iteration j =  9
[1, 2, 3, 4, 7, 6, 10, 5, 8, 9]
Iteration i =  4
Iteration j =  5
Iteration j =  6
Iteration j =  7
Iteration j =  8
Iteration j =  9
[1, 2, 3, 4, 5, 6, 10, 7, 8, 9]
Iteration i =  5
Iteration j =  6
Iteration j =  7
Iteration j =  8
Iteration j =  9
[1, 2, 3, 4, 5, 6, 10, 7, 8, 9]
Iteration i =  6
Iteration j =  7
Iteration j =  8
Iteration j =  9
[1, 2, 3, 4, 5, 6, 7, 10, 8, 9]
Iteration i =  7
Iteration j =  8
Iteration j =  9
[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
Iteration i =  8
Iteration j =  9
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Iteration i =  9
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>>

When you do range(n), It takes values from 0 to n-1. So in your last iteration, it will be array[8] > array[8] — Raghul Raj
– Raghul Raj, Commented Jul 29, 2020 at 15:31
@LazyCoder I said "what if I remove the -1 from the for loop that belongs to the second function. So in that case we would have for i in range(len(array)), thus if the array has 10 elements it goes from 0 to 9 — NaveganTeX
– NaveganTeX, Commented Jul 29, 2020 at 15:35

L.Grozinger · Accepted Answer · 2020-07-29 15:33:49Z

3

Python's range includes the start argument in the range, but excludes the stop argument.

This means that if start and stop are the same, the range will be empty. This is the case in your example if you call select with a list of length 10 and start = 9. The for loop in select is then equivalent to:

for j in range(10, 10):

and since range(10, 10) is empty, the loop will never execute.

So array[10] never happens, and no IndexError is raised.

answered Jul 29, 2020 at 15:33

L.Grozinger

2,3991 gold badge14 silver badges24 bronze badges

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

7 Comments

NaveganTeX Over a year ago

Cool but the range structure is range(start, n-1), thus len(array)` is 10. Then range would go range(10, 10-1)

L.Grozinger Over a year ago

@NaveganTeX the answer refers to the range in the select function, not the one in selection_sort. The range in selection_sort would be range(0, 9), in your given example

L.Grozinger Over a year ago

incidentally, range(10, 10-1) would also be an empty range

L.Grozinger Over a year ago

@NaveganTeX if your selection_sort range is range(len(array)) then your last select range is range(10, 10). If your selection_sort range is range(len(array)-1) then your last select range is range(10, 9).

NaveganTeX Over a year ago

This makes absolute sense. I appreciate it!

|

Luke B · Accepted Answer · 2020-07-29 15:36:37Z

1

If you put a print statement inside your loop in your select function, you'll see that j is never assigned the value 10. Since you can replace the code by for j in range(10, 10) the loop is never executed.

Try it with this

def select(array, start):
    minIndex = start
    print("Start", start)

    for j in range(start + 1, len(array)):
        print(j)
        if array[minIndex] > array[j]:
            minIndex = j

    return minIndex

I assumed that you need to return minIndex at the end of your function, since you assign it inside selection_sort.

You can also try this code to see that it just return an empty list

print(list(range(10, 10)))

answered Jul 29, 2020 at 15:36

Luke B

1,2141 gold badge13 silver badges22 bronze badges

Collectives™ on Stack Overflow

Indexes out of range in selection sort algorithm

2 Answers 2

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related