I am trying the selection sort algorithm. There is the following code:

def selectionSort(list):
   for i in range(len(list)-1):
       curr_min=i
       for j in range(i 1, len(list)):
           if list[j]<list[curr_min]:
               curr_min=j
       temp=list[curr_min]
       list[curr_min]=list[i]
       list[i]=temp

There Is something I don't understand about for loops in general, and I will try to form the question from this example. I understand how the algorithm works. First we assign curr_min the first index [0]. Then for loop iterates over next elements. Let's say that it found an element that is less than the first element. Then current minimum will get assigned the index of that element.

Lets say we have the following array: nums=[3, 5, 2, 4, 6, 1, 8]. Current index is zero, and the element there is 3. Inner for loop starts iterating and finds 2. Current index gets assigned 2(index, not the number).

However, what happens after that? Will the inner loop continue iterating, where it will find element 1 at index 5 and assign that value to the current mininmum?

Or will the inner loop stop and the outer loop get incremented, therefore the curr_min becomes 1 (the second i)? I know this way does not make sense, however, I can't see what's stopping it from doing so either.

Another thing, lets say that the former happened and curr_min got assigned the value of 5. (The index of 1). For curr_min to keep that value, then the outer loop has to stop right? If it continues then curr_min will change to 1 (the second i), and therefore all the things we did in inner loop become useless. Since this code works fine, I'm assuming that does not happen, but again, I can't see what's stopping the outer loop from continuing and assigning it's own values to the variable.

Hope this doesn't sound too gibberish and it's clear what my problem is. Any help is greatly appreciated, Thanks

CodePudding user response：

This whole block runs for every iteration of the outer loop:

curr_min=i
for j in range(i 1, len(list)):
   if list[j]<list[curr_min]:
       curr_min=j
temp=list[curr_min]
list[curr_min]=list[i]
list[i]=temp

Also for every iteration of the outer loop, the inner loop runs to completion. When that inner loop finished, control does not yet return to the outer loop: first the rest of the block is finished. In this case, that is this code:

temp=list[curr_min]
list[curr_min]=list[i]
list[i]=temp

Those lines swap the element at index i with the element at index curr_min. After that, curr_min is not needed anymore. It's value is lost indeed and a new one is used in the next iteration. That's no problem, it has already done its job: indicate which element to swap with the element at index i.

Maybe nested loops where first explained to you with a very simple example like this:

for x in range(0, 10):
    for y in range(0, 20):
        ... # do something with x and y

In that case control does return to the outer loop after the inner loop has finished, simply because there comes nothing after it. But what really happens is the same as always: each block runs completely (except in some cases: raise, continue, break, return) before control returns to the outer statement.

You can use Python Tutor to step through the code (forwards and backwards) and see what happens at every instant, to get a better feel for what's happening: Python Tutor with your code

CodePudding user response：

Loops will continue to iterate until one of:

• the loop end-conditions is met
  • eg In for i in range(x):, when all elements of range(x) have been iterated over.
• a break expression is executed
• an exception is raised
• the process exits, eg sys.exit()
• the function containing the loop, if any, returns.

Lets say we have the following array: nums=[3, 5, 2, 4, 6, 1, 8]. Current index is zero, and the element there is 3. Inner for loop starts iterating and finds 2. Current index gets assigned 2(index, not the number).

However, what happens after that? Will the inner loop continue iterating, where it will find element 1 at index 5 and assign that value to the current mininmum?

The inner loop will continue iterating. It will find element 1 at index 5 and assign that value to the current mininmum, as you say.

Another thing, lets say that the former happened and curr_min got assigned the value of 5. (The index of 1). For curr_min to keep that value, then the outer loop has to stop right?

The outer loop will not stop. Significantly, the outer loop increments a starting index for the inner loop. The inner loop finds the smallest value in the remaining array starting from that index.

Consider the first two iterations of the outer loop. Firstly, the inner loop finds minimum value 1 and it is swapped to index 0. The array is now [1, 5, 2, 4, 6, 3, 8]. This is progress because the minimum element of the array is at the start where it should be in the final output. We can now ignore this first element with value 1 since it's in the right place at index 0. The outer loop increments the starting index of the inner loop from 0 to 1. Now the inner loop repeats again, looking for the smallest value in the array after index 0 and swapping it to index 1. The array is then [1, 2, 5, 4, 6, 3, 8], so again we've made progress... the first two elements are 1,2 in the right place. etc.

CodePudding user response：

I would recommend changing the variable list to a different name. List is a reserved word in Python, so this could cause some problems.