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

Автор: Сара Чен Сара Чен
Hours оновлений

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

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

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

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

Алгоритм сортування вставкою має наступні важливі характеристики:

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

Як працює Insert Operaції роботи?

В алгоритмі Insertion Sort операція вставки використовується для сортування невідсортованих елементів. Це допомагає вставити новий елемент у вже відсортований список.

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

Розглянемо список A з N елементів.

A[N-1] is the element to be inserted in the 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

Insert Operaції роботи

У наведеному вище прикладі новий елемент 6 потрібно вставити у вже відсортований список.

Крок 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++ Програма для сортування вставкою

#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 Код для сортування вставкою

#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 Програма для сортування вставкою

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

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

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

Сортування вставкою не потребує додаткового простору для сортування елементів, складність простору постійна, тобто O(1).

Складність часу

Оскільки сортування вставкою повторює кожен елемент одночасно, для сортування N елементів потрібно N-1 проходів. Для кожного проходу він може робити нульові заміни, якщо елементи вже відсортовані, або замінювати місцями, якщо елементи розташовані в порядку спадання.

  • Для проходу 1 мінімальна необхідна кількість свопів дорівнює нулю, а максимальна – 1.
  • Для проходу 2 мінімальна необхідна кількість свопів дорівнює нулю, а максимальна – 2.
  • Для проходу N мінімальний необхідний своп дорівнює нулю, а максимальний необхідний своп дорівнює N.
  • Мінімальний своп дорівнює нулю, тому найкраща часова складність O(N) для ітерації N проходів.
  • Загальна кількість максимальних свопів становить (1+2+3+4+..+N) i. N(N+1)/2, найгірша часова складність – O(N^2).

Ось важлива часова складність сортування вставки:

  • Найгірша складність: O(n2): Сортування масиву в порядку спадання, коли він знаходиться в порядку зростання, є найгіршим сценарієм.
  • Найкраща складність випадку: O(n): Складність у найкращому випадку виникає, коли масив уже відсортовано, зовнішній цикл виконується n разів, тоді як внутрішній цикл не виконується взагалі. Є лише n кількість порівнянь. Отже, у цьому випадку складність є лінійною.
  • Середня складність справи: O(n2): Це трапляється, коли елементи масиву розташовуються в перемішаному порядку, який не є ні зростаючим, ні спадним.

Підсумки

  • Сортування вставкою — це метод алгоритму сортування, який базується на порівнянні.
  • Це стабільний метод сортування, тому він не змінює відносний порядок рівних елементів.
  • Для кожного елемента використовується операція вставки, щоб вставити елемент у відсортований підсписок.
  • Сортування вставкою — це алгоритм сортування на місці.
  • Найгірша та середня часова складність сортування вставкою є квадратичною, тобто O(N^2).
  • Сортування вставкою не потребує допоміжного простору.