CODEWITHSUNDEEP
pythonalgorithmsorting
Questions
Questions

Reputation: 99

selection sort not understanding this code

I found this code online for the selection sort:

 def selectionSort(alist):
    for fillslot in range(len(alist)-1,0,-1):
        positionOfMax=0
        for location in range(1,fillslot+1):
            if alist[location]>alist[positionOfMax]:
                positionOfMax = location

        temp = alist[fillslot]
        alist[fillslot] = alist[positionOfMax]
        alist[positionOfMax] = temp

 alist = [54,26,93,17,77,31,44,55,20]
 selectionSort(alist)
 print(alist)

list length = 9

i dont understand these lines of code: 

 for fillslot in range(len(alist)-1,0,-1):

and

 for location in range(1,fillslot+1):

for fillslot if we go from those ranges it means we are looking at index: 8,7,6,5,4,3,2,1 why do we not look at index 0?

also for the location variable we would be looking at 1,2,3,4,...fillslot again why are we not looking at index 0?

Upvotes: 0

Views: 285

Answers (1)

mahbubcseju
mahbubcseju

Reputation: 2290

Using for fillslot in range(len(alist)-1,0,-1):, we are looking at index from right to left. When we are at a position (i), we will find the maximum number from index 0 to index i and swap the maximum number with element alist[i].

If we do so, then all the elements with index from 0 to i is smaller than all the elements with index i+1 to len(alist)-1.

After processing for index 1 , alist[0] will be smaller than any element from 1 to len(alist)-1, So we don,t need to consider index 0.

Now using for location in range(1,fillslot+1):, we are finding the maximum number from index 0 to index i. To find the maximum number firstly we let 0 index's number as maximum.For this, we declare a variable called positionOfMax=0 to hold the index of maximum number. Then we compare others numbers from position 1 to i, and are updating the positionOfMax variable.

For example,

alist=[2,5,3,9]

To find the maximum number of from index 0 to index 2:
let positionOfMax=0; which means let maximum number is at position 0.
Now check positions from 1 to 2.

When we are at position 1, alist[1] is greater than alist[positionOfMax], so positionOfMax will be updated by 1. Now positionOfMax is 1.

When we are at position 2, alist[1] is smaller than alist[positionOfMax], so positionOfMax will not be updated. So positionOfMax is still 1.

So maximum number from index 0 to index 2 is at position 1. I think now it is clear why the for loops are avoiding index 0.

Upvotes: 1

Related Questions