Алгоритм сортування вставками з C, C++, Java, Python прикладів

Що таке сортування вставкою?

Сортування вставками — це один із алгоритмів сортування порівнянням, який використовується для сортування елементів шляхом ітерації по одному елементу за раз та розміщення елемента в правильній позиції в межах уже впорядкованої області.

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

Оскільки сортування вставками формує результат поступово, його інтуїтивно зрозуміло навчати, легко налагоджувати та є надійною основою для дуже малих вхідних даних, де складніші алгоритми додавали б накладних витрат без помітних переваг.

Характеристики алгоритму сортування вставкою

Алгоритм сортування вставками має такі важливі характеристики, які пояснюють його поведінку на реальних робочих навантаженнях:

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

З огляду на ці особливості, у наступному розділі пояснюється основна операція вставки, яка забезпечує кожен прохід алгоритму.

Як працює Insert 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++, 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). Сортування вставками є одним з адаптивних алгоритмів сортування.

Складність сортування вставкою

Наведене нижче обговорення складності охоплює як використання пам'яті, так і час виконання, тому ви можете позиціонувати сортування вставками порівняно з такими альтернативами, як Bubble Сортування та Швидке сортування.

Складність простору

Сортування вставками не потребує додаткового простору для сортування елементів. Просторова складність є постійною, тобто 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): Це трапляється, коли елементи масиву розташовані у перемішаному порядку, який не є ні зростаючим, ні спадаючим.

Поширені запитання