Сортиране чрез вмъкване: Алгоритъм с C, C++, Java, Python Примери
Сара Чен
Какво е сортиране чрез вмъкване?
Сортирането чрез вмъкване е един от алгоритмите за сортиране при сравнение, използвани за сортиране на елементи чрез повторение на елемент по един и поставяне на елемента в правилната му позиция.
Всеки елемент се вмъква последователно във вече сортиран списък. Размерът на вече сортирания първоначално списък е единица. Алгоритъмът за сортиране чрез вмъкване гарантира, че първите k елемента са сортирани след k-тата итерация.
Характеристики на алгоритъма за сортиране чрез вмъкване
Алгоритъмът за сортиране чрез вмъкване има следните важни характеристики:
- Това е стабилна техника за сортиране, така че не променя относителния ред на равни елементи.
- Той е ефективен за по-малки набори от данни, но не е ефективен за по-големи списъци.
- Сортирането чрез вмъкване е адаптивно, което намалява общия брой стъпки, ако е частично сортирано. Array се предоставя като вход, за да бъде ефективен.
Как работи Insert Operaция работа?
В алгоритъма за сортиране чрез вмъкване операцията за вмъкване се използва за сортиране на несортирани елементи. Помага да вмъкнете нов елемент във вече сортиран списък.
Псевдокод на операцията за вмъкване:
Да разгледаме списък 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
В горния пример нов елемент 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-1 преминавания за сортиране на N елемента. За всяко преминаване може да направи нулеви размени, ако елементите вече са сортирани, или да размени, ако елементите са подредени в низходящ ред.
- За преминаване 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бобщение
- Сортирането чрез вмъкване е метод на алгоритъм за сортиране, който се основава на сравнението.
- Това е стабилна техника за сортиране, така че не променя относителния ред на равни елементи.
- Във всеки елемент операцията за вмъкване се използва за вмъкване на елемента в сортирания подсписък.
- Сортирането чрез вмъкване е алгоритъм за сортиране на място.
- Най-лошата и средна времева сложност на сортирането при вмъкване е квадратична, т.е. O(N^2).
- Сортирането чрез вмъкване не изисква допълнително пространство.