0

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.

Improve this question
11
  • Not sure if I understand your first question: minimum_index is set to 0 right before the second loop. So, before updating it, you are indeed doing the comparison against arr[0]. Commented Sep 11, 2022 at 17:32
  • Second question: for a given x, chosen in the outer loop, once you got the index y that you want to swap, you do the swapping. The purpose of the inner loop is to get the index y for minimum arr[y]. If you were to make the swap before finishing the inner loop, you could do many swaps before getting the right y. Commented Sep 11, 2022 at 17:37
  • For a visual example, I would put the swap inside the inner loop, and add a printing statement right after that, so you can see what happens in each iteration of the inner loop. Commented Sep 11, 2022 at 17:39
  • BTW, I tried it and didn't get my list sorted. I used [35, 68, 16, 84, 2, 46]. Did you tried the original code before changing it? Maybe it's because of your changes? Commented Sep 11, 2022 at 17:44
  • 1
    I think the problem you are having is your thinking about what minimum is. The minimum of concern changes as the algorithm progresses. The initial minimum is the actual smallest of all. Once that has been identified, the minimum of concern changes to the next smallest. This is also why only one swap is needed per round of the outer loop: Each round of the outer loop identifies a small value and the x values guards these against further swaps, ie it keeps a barrier between those that are sorted and those yet to be sorted. Commented Sep 11, 2022 at 17:49

1 Answer 1

Reset to default
1

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]
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Ohhhh I think I understand the second question I asked. So from my understanding of it, you only want to swap once when two elements have been compared, hence why it's done within the outer loop. So for example, if we have a list of [5,3,6,2], we would compare the first element with the others, and since 3 occurred first and is smaller than 5, both would swap, instead of 5 swapping with 3, and then 3 swapping with 2, all in one inner loop?
Nope, in your example, is going to take 5, and compare it with every other through the second loop. Because 2 is the smallest, is going to swap 2 with 5, so you'll get [2, 3, 6, 5]. Now, because we know 2 is the smallest of all the smaller-than-five, there's no sense on comparing 2 with the rest anymore! See the version of my code with printed numbers. I edited it with your example :)
But how would it know 2 is the smallest, since there's an if statement that checks whether arr[y] is smaller than the current arr[x] and since 3 is smaller than 5, wouldn't it swap it round?
It checks whether arr[y] is amaller than arr[minimum_index] (which is arr[x] at first, but then get updated). Once a smaller is find, minimum_index changes to y, in the inner loop. So: first it finds that 3 < 5, but because it's still in the inner loop, it keeps comparing without swapping. Then, it finds 2 < 3, and changes minimum_index again. After the inner loop is completed, it makes the swap for the last minimum_index it found to be smaller.
Exactly, because... the swap happens in the outer loop!! ; )
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.