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]

CodePudding user response：

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)

CodePudding user response：

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.