Selection Sort and Nested For Loop Python

Hahaha2411 0
Viewed 38

I understand the concept of Selection Sort (I think) but what I'm confused about is trying to code it. From my understanding of Selection Sort, you set the first element as your minimum value and then compare it with the second element, and if the second element is smaller, you swap the elements together, making the second element your minimum value, and the previous min value goes to the position of where the second element was but if not, you continue looping through the list. You keep doing this until the list has been sorted.

def selection_sort(arr):
    for x in range(len(arr)):
        minimum_index = 0
        for y in range(x+1, len(arr)):
            print(arr[minimum_index], arr[y])
            if arr[y] < arr[minimum_index]:
                minimum_index = y
        arr[x], arr[minimum_index] = arr[minimum_index], arr[x]
    return arr

I copied a code online, and changed it a bit to try and understand it. My question is, why can't minimum_index be equal to 0 if you're trying to compare it to other elements, and then swapping it. And also, why is arr[x], arr[minimum_index] = arr[minimum_index], arr[x] within the outer for loop body and not inside the inner for loop.

Is it also possible to try and explain in terms a beginner would understand and also maybe some example.

Sorry if any of the questions sound stupid. I'm still trying to understand Data Structures and Algorithms.

selection-sort python
1 Answers

The working code uses minimum_index = x instead of minimum_index = 0:

def selection_sort(arr):
    for x in range(len(arr)):
        minimum_index = x
        for y in range(x+1, len(arr)):
            print(arr[minimum_index], arr[y])
            if arr[y] < arr[minimum_index]:
                minimum_index = y
        arr[x], arr[minimum_index] = arr[minimum_index], arr[x]
    return arr

Let's start by answering your second question, and I think that would make the first one clearer:

For a given index x, chosen in the outer loop, once you got the index y that corresponds to the minimum element lesser than arr[x], if there's one, you do the swap. The purpose of the inner loop is to get the index y for minimum arr[y], not to swap once for every number lesser than arr[x], but only for the minimum number lesser than arr[x]. If you were to make the swap before finishing the inner loop, you could do many swaps before getting the right y. And that's why the swapping must occur in the outer loop, once the inner loop made it's job.

Now, once you have the minimum in the right position, you don't need to evaluate that position anymore, because now you know there's no other arr[y] lesser than this one.

Note that minimum_index was indeed equal to 0 in the first iteration of the outer loop.

To see it step by step, I modified it so it only prints the arrays at the beginning and in each iteration:

arr = [5,3,6,2]

def selection_sort(arr):
    print(arr)
    for x in range(len(arr)):
        minimum_index = x
        for y in range(x+1, len(arr)):
            if arr[y] < arr[minimum_index]:
                minimum_index = y
        arr[x], arr[minimum_index] = arr[minimum_index], arr[x]
        print(arr)
    # return arr   # commented so last line doesn't get printed twice

selection_sort(arr)

[5, 3, 6, 2]
[2, 3, 6, 5]
[2, 3, 6, 5]
[2, 3, 5, 6]
[2, 3, 5, 6]
Ignatius Reilly0
Related