Номер §1.5 ПМ 10

В примере дан массив A = [, , , , , , , ]. Для каждого индекса i найдём наибольшее значение среди элементов от i до конца массива. Переменная imax хранит индекс наибольшего из просмотренных элементов. Сравниваем очередной элемент с найденным максимумом и, если нужно, обновляем индекс. Затем меняем элементы с индексами i и imax местами.

A = [, , , , , , , ]
N = len(A)
for i in range(N - ):
    imax = i
    for j in range(i + , N):
        if A[j] > A[imax]:
            imax = j
    A[i], A[imax] = A[imax], A[i]
print(A)

Ход обменов подтверждает результат: сначала переходит на место , затем — на место , затем — на место . После следующих обменов начало массива становится , , , , , , а оставшиеся , уже стоят в нужном порядке. Программа выводит [, , , , , , , ].

Подпрограмма max получает два индекса и возвращает индекс элемента с большим значением. Это важно: для обмена нужны места элементов в массиве, а не только их значения. При равенстве оставляем первый индекс.

def max(A, left, right):
    if A[right] > A[left]:
        return right
    return left

A = [, , , , , , , ]
N = len(A)
for i in range(N - ):
    imax = i
    for j in range(i + , N):
        imax = max(A, imax, j)
    A[i], A[imax] = A[imax], A[i]
print(A)

При каждом вызове max сравниваются два элемента: текущий максимум неотсортированной части и следующий элемент. Поэтому после внутреннего цикла imax указывает на максимальный элемент этой части. Обе программы выводят один и тот же массив по невозрастанию.