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

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

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

Вот модифицированная процедура сортировки вставкой в ​​Python:

def insertion_sort_nonincreasing(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] < key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

В этой версии, когда arr[j] < keyравен True, мы меняем arr[j + 1]на arr[j]. Это гарантирует, что более крупные элементы будут перемещены к началу массива, что приведет к невозрастающему порядку.

Альтернативный подход.
Другой способ добиться невозрастающего порядка с помощью сортировки вставками — перевернуть входной массив перед применением исходного алгоритма. Такой подход устраняет необходимость модификации операции сравнения. Вот пример кода:

def insertion_sort_nonincreasing_reverse(arr):
    arr.reverse()
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

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

В этой статье мы рассмотрели, как изменить алгоритм сортировки вставками для сортировки элементов в невозрастающем порядке. Мы предоставили два примера кода: один путем изменения операции сравнения внутри алгоритма, а другой — путем изменения входного массива. Оба подхода достигают желаемого результата. Поняв, какие изменения необходимы, вы сможете легко адаптировать другие алгоритмы сортировки для сортировки элементов в невозрастающем порядке.

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