Почему этот алгоритм может сортировать данные в порядке убывания

Question

Я изучаю программирование на Python и пытаюсь отсортировать данные в порядке убывания. # sort1 ниже успешно отсортирован, но я не могу понять, почему это произошло. Также, data[i], data[data.index(mn)] = data[data.index(mn)], data[I] является подозрительным пунктом.

data = [-1.48,  4.96,  7.84, -4.27,  0.83,  0.31, -0.18,  3.57,  1.48,  5.34,
         9.12,  7.98, -0.75,  2.22, -1.16,  6.53, -5.38,  1.63, -2.85,  7.89,
        -5.96, -8.23,  8.76, -2.97,  4.57,  5.21,  9.43,  3.12,  6.52,  1.58 ]
#sort1

for i in range(30):
    mn = data[i]
    for j in data:
        if j < mn:
            mn = j
            data[i], data[data.index(mn)] = data[data.index(mn)], data[i]
        else:
            pass
print('ascending order1:')
print(data)

Answer 1

Это сортировка вставки https://en.wikipedia.org/wiki/Insertion_sort

Вы можете представить себе, как будто сортируете потоковый список элементов:

for i in range(30): # for each item streamed here
    mn = data[i]    # take the new item (if exists new item)
    for j in data:  # find its place in the sorted data, and insert it there:
        if j < mn:  # if found its place, insert it here
            mn = j  
            data[i], data[data.index(mn)] = data[data.index(mn)], data[i] 

ОБНОВЛЕНИЕ

Интуиция, стоящая за сортировкой вставок, заключается в том, что вы обновляете ранее отсортированный список каждый раз, когда получаете новый элемент. Таким образом, вам не нужно беспокоиться о позиции сортировки будущих предметов.

Так как данные до времени i отсортированы, то после нахождения первого обмена все элементы будут поменяться местами, пока не наступит время i.

Теперь проблема скоманда подкачки:

data[i], data[data.index(mn)] = data[data.index(mn)], data[i] 

Эта команда подкачки фактически игнорирует будущие перестановки (когда data.index(mn) больше текущего времени i). Однако, поскольку он работает, когда время i больше, чем data.index(mn), этого достаточно для сортировки при вставке. Это пример:

# two attempts to swapping x and y: 
data = ['x', 'y']

# ignored (target of swap is at time i, found position in future!):
i = 0; mn = 'y' # data.index(mn) == 1
data[i], data[data.index(mn)] = data[data.index(mn)], data[i] 
print('ignored swap', data) 

# success (target of swap is at time i, found position in past (before i)):
i = 1; mn = 'x' # data.index(mn) == 0
data[i], data[data.index(mn)] = data[data.index(mn)], data[i] 
print('success swap', data)

Answer 2

В вашем коде есть 2 ошибки:

1. В цикле лучше выполнить for i in range(len(data)), поэтому, если размер переменной изменится данные , ваш кодбудет работать.
2. Ваш код сортирует данные в в порядке убывания , поэтому вы должны вывести: print('descending order1:')

Теперь давайте поговорим об части алгоритма. Фактически, ваш код - это реализация алгоритма сортировки пузырьковая сортировка , также известная как тонущая сортировка . Этот алгоритм последовательно просматривает список и сравнивает смежные элементы. Он меняет местами соседние элементы, если они находятся в неправильном порядке (т. Е. Если первый элемент уступает второму). Это происходит до тех пор, пока список не будет отсортирован (в порядке убывания). Вы можете получить больше понимания здесь

Код data[i], data[data.index(mn)] = data[data.index(mn)], data[i] - это просто часть swap . Это Pythonic способ поменять элементы. Например:

a = 5
b = 15
a, b = b, a # swap 'elegantly a and b
print(a) #  display 15
print(b) # display 5

Комментарии к коду:

for i in range(30): # first cursor: steps through the indexes of the list
    mn = data[i]    # assigns the data at index i to the variable mn
    for j in data:  # second cursor: steps through the data of the list
        if j < mn:  # compares adjacent elements
            mn = j  
            data[i], data[data.index(mn)] = data[data.index(mn)], data[i] # swap adjacent elements
        else: # if the first data superior to the second, don't do anything
            pass