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

Какво е сортиране чрез вмъкване?

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

Всеки елемент се вмъква последователно във вече сортиран списък. Първоначалният размер на вече сортирания списък е единица. Алгоритъмът за сортиране чрез вмъкване гарантира, че първите k елемента са сортирани след k-тата итерация на външния цикъл.

Тъй като сортирането с вмъкване изгражда резултата постепенно, то е интуитивно за обучение, лесно за отстраняване на грешки и е солидна основа за много малки входни данни, където по-сложни алгоритми биха добавили режийни разходи без измерими ползи.

Характеристики на алгоритъма за сортиране чрез вмъкване

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

• Това е стабилна техника за сортиране, така че не променя относителния ред на равни елементи.
• Той е ефикасен за по-малки набори от данни, но не е ефективен за по-големи списъци, където доминира квадратичният растеж.
• Сортирането чрез вмъкване е адаптивно, което намалява общия брой стъпки, ако входните данни са частично сортирани. Array се предоставя като вход, за да бъде ефективен, тъй като произволният достъп позволява постоянни времеви отмествания по време на вътрешния цикъл.
• Това е алгоритъм, работещ на място, така че не изисква спомагателно съхранение, пропорционално на размера на входните данни.

Имайки предвид тези характеристики, следващият раздел обяснява основната операция за вмъкване, която захранва всеки проход на алгоритъма.

Как работи 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-1 преминавания за сортиране на N елемента. За всяко преминаване може да се направят нула размени, ако елементите вече са сортирани, или може да се наложи много размени, ако елементите са подредени в низходящ ред.

• За преминаване 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): Това се случва, когато елементите на масива се срещат в разбъркан ред, който не е нито възходящ, нито низходящ.

Въпроси и Отговори