problem with sorting array with native method

Question

my method for sorting an array written in python:

array = [3, 2, 1]

for i in range(len(array)):
    minVal = array[i]
    for j in range(i + 1, len(array)):
        if (array[j] < array[i]):
            if (array[j] <= minVal):
                minVal = array[j]
    if i < len(array) - 1:
        array[i + 1] = array[i]
        array[i] = minVal

print(array)

how do i think it works?
the first cycle will be executed 3 times
first iteration:

#i will check number 3 with numbers 2 and 1
#expected output:
minVal = 1
array = [1, 3, 2]

second iteration:

#i will check number 3 with number 2
#expected output:
minVal = 2
array = [1, 2, 3]

last iteration:

#I do not know if he is needed.
#perhaps it is worth writing `range(len(array) - 1)` in the first loop?
#and because of this iteration, I also added the check `if i <len (array) - 1:`

expected output at the end: [1, 2, 3]
what i got: [1, 1, 3]

`if (array[j] < array[i]):` isn't needed and the condition at the end doesn't make sense. Are you trying to write [selection sort](https://en.wikipedia.org/wiki/Selection_sort)? — ggorlen, Jan 12 '22 at 15:54
I try to write as I think in my head, I do not take an example from different algorithms — np., Jan 12 '22 at 15:57
Please read about [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/). You can also use [Python-Tutor](http://www.pythontutor.com/visualize.html#mode=edit) which helps to visualize the execution of the code step-by-step. — Tomerikoo, Jan 12 '22 at 15:58
You should also read about [bubble sort](https://en.wikipedia.org/wiki/Bubble_sort) which you were on the verge of doing without knowing — Tomerikoo, Jan 12 '22 at 16:24

score 1 · Accepted Answer · answered Jan 12 '22 at 16:13

Think about your logic: You find the minimum value and then replace the i item with it but only advance the i item one index ahead to i+1. By doing so, after the first iteration you have the list as [1, 3, 1]. Let's break it down:

you start with [3, 2, 1]
minVal = array[i] = 3
After the j loop we find that minVal = 1
Now we do array[i + 1] = array[i] -> array[1] = 3. So now we have [3, 3, 1].
Now we do array[i] = minVal -> array[0] = 1. So now we have [1, 3, 1].

The element 2 has disappeared from the list!

To fix this, you need to save the minVal's index and replace the two items, not override another item:

array = [3, 2, 1]

for i in range(len(array)):
    minIndex = i
    for j in range(i + 1, len(array)):
        if (array[j] < array[i]):
            if (array[j] <= array[minIndex]):
                minIndex = j
    minVal = array[minIndex]
    if i < len(array) - 1:
        array[minIndex] = array[i]
        array[i] = minVal

print(array)

Now there are some points to simplify and improve your code:

There is no need to check that array[j] < array[i] on every iteration - in the first iteration it is equal to minVal/array[minIndex] anyway, so you can remove one if.
There is no need for the last if - instead of checking every iteration if we got to the last element, just remove it from the loop - for i in range(len(array)-1).
The replacement can be done in one line without the need to even save minVal - see this SO question.

So the improved version according to the above can be:

array = [3, 2, 1]

for i in range(len(array)-1):
    minIndex = i
    for j in range(i + 1, len(array)):
        if array[j] < array[minIndex]:
            minIndex = j

    array[minIndex], array[i] = array[i], array[minIndex]

print(array)

score 0 · Answer 2 · answered Jan 12 '22 at 16:03

You are currently searching an array for the minimum value including and past the current index. This is an O(N^2) approach, and quite robust. However, you need to implement it correctly.

The check

if (array[j] < array[i]):
        if (array[j] <= minVal):

is redundant. You shouldn't restrict your test by the original minimum value, although it does no harm, since minVal <= array[i] in all cases.

You don't really care about the value of minVal as much as you do about its location. You more-or-less correctly identify minVal as array[j], but then you swap it out as array[i + 1] = array[i]. Where is the correct j recorded?

Here is the same idea, but without the extra check, and using minJ to illustrate the caching of j vs the value:

array = [3, 2, 1]

for i in range(len(array) - 1):       # Don't bother iterating the last element
    min_j = i                         # Only record indices
    for j in range(i + 1, len(array)):
        if array[j] < array[min_j]:   # Only test current minimum
            min_j = j
    array[i], array[min_j] = array[min_j], array[i]

print(array)

Couple of small tweaks:

You don't need to iterate over the last element, so shorten the outer range by one.
The idiomatic way to swap two quantities in python is x, y = y, x. If you're going to use a temporary variable anyway, it may as well be a tuple that enhances legibility.

problem with sorting array with native method

2 Answers2