Алгоритм сортировки вставками на языке C. C++, Java, Python Примеры

Что такое сортировка вставками?

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

Каждый элемент последовательно вставляется в уже отсортированный список. Размер уже отсортированного списка изначально равен единице. Алгоритм сортировки вставками гарантирует, что первые k элементов будут отсортированы после k-й итерации внешнего цикла.

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

Характеристики алгоритма сортировки вставками

Алгоритм сортировки вставками обладает следующими важными характеристиками, объясняющими его поведение в реальных условиях:

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

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

Как работает вставка Operaционная работа?

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

Псевдокод операции вставки:

Рассмотрим список A из N элементов.

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

В приведенном выше примере в уже отсортированный список вставляется новый элемент 6. Следующие шаги tracВнутренний цикл замыкается по мере того, как новый элемент перемещается влево к своему правильному положению.

Шаг 1) По сравнению с соседним слева элементом A[5], 9 > 6, мы меняем местами позиции 9 и 6. Теперь элемент 6 перемещается в A[4].

Шаг 2) Теперь сравним A[4] и A[3] и обнаружим, что A[3] > A[4], поэтому снова поменяем местами 6 и 8.

Шаг 3) Теперь сравним A[3] и A[2]. Поскольку A[2] > A[3], поменяем местами 7 и 6.

Шаг 4) Мы сравниваем A[1] и A[2]. Поскольку A[1] < A[2], левый смежный элемент больше не больше. Мы делаем вывод, что 6 вставлено правильно, и на этом останавливаем внутренний цикл.

Как работает сортировка вставками

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

На рисунке выше показана работа алгоритма сортировки вставками в структуре данных. Изначально в отсортированном подсписке находится только один элемент, т.е. 4. После вставки A[1], т.е. 3, размер отсортированного подсписка увеличивается до 2, и алгоритм продолжает эту последовательность до тех пор, пока не будут размещены все элементы.

После определения концептуальной схемы, в следующих разделах представлены конкретные примеры реализации. C++, С и Python Таким образом, вы можете сравнивать структуры циклов в разных языках.

C++ Программа для сортировки вставками

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

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

Выход:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code для сортировки вставками

Та же логика напрямую применима и к языку C. Стандарт printf вызовы заменяют вывод потока, но схема обмена внутри внутреннего цикла идентична C++ версия.

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Выход:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Программа для сортировки вставками

Python поддерживает обмен кортежамиping в одном выражении, поэтому внутренний цикл более компактен, чем его C и C++ аналоги, сохраняя при этом то же алгоритмическое поведение.

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Выход:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Свойства сортировки вставками

Вот важные свойства сортировки вставками, которые помогут вам решить, когда она является подходящим инструментом:

• В сети: Сортировка вставками позволяет сортировать элементы по мере их поступления. Если список элементов уже отсортирован и мы добавляем в него новые элементы, то нет необходимости запускать всю процедуру сортировки заново. Вместо этого мы перебираем только вновь добавленные элементы.
• На месте: Пространственная сложность алгоритма сортировки вставками постоянна и не требует дополнительного места. Этот алгоритм сортирует элементы на месте.
• Стабильная: В сортировке вставками элементы не меняются местами, если их значения равны. Например, если два элемента, x и y, равны, и x стоит перед y в несортированном списке, то в отсортированном списке x все равно будет стоять перед y. Это делает сортировку вставками стабильной.
• Адаптивный: A алгоритм сортировки Алгоритм считается адаптивным, если он выполняется быстрее, когда входные элементы или их подмножество уже отсортированы. Как мы обсуждали выше, лучшее время выполнения сортировки вставками составляет O(N), а худшее — O(N^2). Сортировка вставками — один из адаптивных алгоритмов сортировки.

Сложность сортировки вставками

Приведенное ниже обсуждение сложности охватывает как использование памяти, так и время выполнения, поэтому вы можете сравнить сортировку вставками с альтернативными методами, такими как... Bubblэлектронная сортировка и Быстрая сортировка.

Космическая сложность

Сортировка вставками не требует дополнительного пространства для сортировки элементов. Пространственная сложность постоянна, т.е. O(1), поскольку используется лишь несколько временных переменных независимо от размера входных данных.

Сложность времени

Поскольку сортировка вставками обрабатывает по одному элементу за раз, для сортировки N элементов требуется N-1 проходов. На каждом проходе может не быть ни одной перестановки, если элементы уже отсортированы, или может потребоваться много перестановок, если элементы расположены в порядке убывания.

• Для прохода 1 минимальное необходимое количество свопов равно нулю, а максимальное необходимое количество свопов равно 1.
• Для прохода 2 минимальное необходимое количество свопов равно нулю, а максимальное необходимое количество свопов равно 2.
• Для прохода N минимальный требуемый обмен равен нулю, а максимальный требуемый обмен равен N.
• Минимальная замена равна нулю, поэтому наилучшая временная сложность равна O(N) для итерации N проходов.
• Общее максимальное количество обменов составляет (1+2+3+4+…+N), т.е. N(N+1)/2, поэтому наихудшая временная сложность составляет O(N^2).

Вот важная временная сложность алгоритма сортировки вставками:

• Наихудшая сложность случаяСложность O(n^2): сортировка массива в порядке убывания, когда требуется сортировка в порядке возрастания, является наихудшим сценарием.
• лучшая сложность дела: O(n): Наилучший случай достигается, когда массив уже отсортирован; внешний цикл выполняется n раз, а внутренний цикл не выполняется вообще. Всего n сравнений, поэтому сложность линейная.
• Средняя сложность дела: O(n^2): Это происходит, когда элементы массива расположены в перемешанном порядке, который не является ни восходящим, ни нисходящим.

Часто задаваемые вопросы (FAQ)