Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Сортування включенням або сортування вставлянням — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:
- простота у реалізації
- ефективний (зазвичай) на маленьких масивах
- ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій
- на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною
- є стабільним алгоритмом
 | |
| Клас | Алгоритм сортування |
|---|---|
| Структура даних | масив |
| Найгірша швидкодія | О(n2) |
| Найкраща швидкодія | О(n) |
| Середня швидкодія | О(n2) |
| Просторова складність у найгіршому випадку | О(n), O(1) |
| Оптимальний | Переважно ні |
Наприклад, більшість людей при сортуванні колоди гральних карт, використовують метод, схожий на алгоритм сортування включенням.
Опис
На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію у вже відсортованому списку доти, доки набір вхідних даних не буде вичерпано. Метод вибору чергового елементу з початкового масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються за порядком їх появи у вхідному масиві.
Реалізація
for i := 2 to arrayLength do begin key := arr[i]; j := i; while (j > 1) and (arr[j - 1] > key) do begin {обмін елементів} tempValue := arr[j]; arr[j] := arr[j - 1]; arr[j - 1] := tempValue; j := j - 1; end; arr[j] := key; end; #include <iostream> #include<ctime> using namespace std; const int Nmax = 100000; void InsertSort(int arr[], int n) { int key, i; for (int k = 1; k < n; k++) { key = arr[k]; i = k - 1; while ((i >= 0)&&(arr[i]>key)) { arr[i + 1] = arr[i]; i = i - 1; } arr[i + 1] = key; } } int main() { int n = 0; cout << "Rozmir: "; cin >> n; int arr[Nmax]; srand(time(NULL)); for (int i = 0; i < n; i++){ arr[i] = rand()% 10; } for (int i = 0; i < n; i++){ cout << arr[i] << " "; } cout << endl; cout << "InsertSort:" << endl; InsertSort(arr, n); for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; system("pause"); } Див. також
Примітки
- Вступ до алгоритмів, 2019, с. 35.
Джерела
- Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — .(англ.)
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 2.1: Сортування вставлянням. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
Посилання
- Animated Sorting Algorithms: Insertion Sort — графічна демонстрація роботи алгоритму
- Category: Insertion Sort — LiteratePrograms — приклади реалізації алгоритму на різних мовах програмування.
- Сортування включенням
 | Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Sortuvannya vklyuchennyam abo sortuvannya vstavlyannyam prostij algoritm sortuvannya na osnovi porivnyan Na velikih masivah ye znachno mensh efektivnim za taki algoritmi yak shvidke sortuvannya piramidalne sortuvannya ta sortuvannya zlittyam Odnak maye cilu nizku perevag prostota u realizaciyi efektivnij zazvichaj na malenkih masivah efektivnij pri sortuvanni masiviv dani v yakih vzhe nepogano vidsortovani produktivnist rivna O n d de d kilkist inversij na praktici efektivnishij za bilshist inshih kvadratichnih algoritmiv O n2 yak to sortuvannya viborom ta sortuvannya bulbashkoyu jogo shvidkodiya rivna n2 4 i v najkrashomu vipadku ye linijnoyu ye stabilnim algoritmomSortuvannya vklyuchennyamPriklad sortuvannya masivu vipadkovih chisel KlasAlgoritm sortuvannyaStruktura danihmasivNajgirsha shvidkodiyaO n2 Najkrasha shvidkodiyaO n Serednya shvidkodiyaO n2 Prostorova skladnist u najgirshomu vipadkuO n O 1 OptimalnijPerevazhno ni Napriklad bilshist lyudej pri sortuvanni kolodi gralnih kart vikoristovuyut metod shozhij na algoritm sortuvannya vklyuchennyam Priklad sortuvannya vklyuchennyam Elementi v chornih ramkah posortovana chastina spisku Metod porivnyuye nastupnij element neposortovanoyi chastini chervona ramka z poslidovnimi elementami posortovanoyi ta vstavlyaye u potribne misce OpisNa kozhnomu kroci algoritmu mi vibirayemo odin z elementiv vhidnih danih i vstavlyayemo jogo na potribnu poziciyu u vzhe vidsortovanomu spisku doti doki nabir vhidnih danih ne bude vicherpano Metod viboru chergovogo elementu z pochatkovogo masivu dovilnij mozhe vikoristovuvatisya praktichno bud yakij algoritm viboru Zazvichaj i z metoyu otrimannya stijkogo algoritmu sortuvannya elementi vstavlyayutsya za poryadkom yih poyavi u vhidnomu masivi RealizaciyaPascal for i 2 to arrayLength do begin key arr i j i while j gt 1 and arr j 1 gt key do begin obmin elementiv tempValue arr j arr j arr j 1 arr j 1 tempValue j j 1 end arr j key end C include lt iostream gt include lt ctime gt using namespace std const int Nmax 100000 void InsertSort int arr int n int key i for int k 1 k lt n k key arr k i k 1 while i gt 0 amp amp arr i gt key arr i 1 arr i i i 1 arr i 1 key int main int n 0 cout lt lt Rozmir cin gt gt n int arr Nmax srand time NULL for int i 0 i lt n i arr i rand 10 for int i 0 i lt n i cout lt lt arr i lt lt cout lt lt endl cout lt lt InsertSort lt lt endl InsertSort arr n for int i 0 i lt n i cout lt lt arr i lt lt cout lt lt endl system pause Div takozhSpisok algoritmivPrimitkiVstup do algoritmiv 2019 s 35 DzherelaDonald Knut Sorting and Searching The Art of Computer Programming 3rd Massachusetts Addison Wesley 1998 T 3 780 s ISBN 0 201 89685 0 angl T Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 Rozdil 2 1 Sortuvannya vstavlyannyam Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 PosilannyaAnimated Sorting Algorithms Insertion Sort grafichna demonstraciya roboti algoritmu Category Insertion Sort LiteratePrograms prikladi realizaciyi algoritmu na riznih movah programuvannya Sortuvannya vklyuchennyam Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi