www.wikidata.uk-ua.nina.az

Сортування включенням або сортування вставлянням 1 простий алгоритм сортування на основі порівнянь На великих масивах є

Сортування включенням

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

  • простота у реалізації
  • ефективний (зазвичай) на маленьких масивах
  • ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій
  • на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною
  • є стабільним алгоритмом
Сортування включенням
Приклад сортування масиву випадкових чисел.
Клас Алгоритм сортування
Структура даних масив
Найгірша швидкодія О(n2)
Найкраща швидкодія О(n)
Середня швидкодія О(n2)
Просторова складність у найгіршому випадку О(n), O(1)
Оптимальний Переважно ні

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

Приклад сортування включенням. Елементи в чорних рамках — посортована частина списку. Метод порівнює наступний елемент непосортованої частини (червона рамка) з послідовними елементами посортованої та вставляє у потрібне місце.

Опис ред.

На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію у вже відсортованому списку доти, доки набір вхідних даних не буде вичерпано. Метод вибору чергового елементу з початкового масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються за порядком їх появи у вхідному масиві.

Реалізація ред.

Pascal 

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;

C++

#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"); }

Див. також ред.

Примітки ред.

  1. Вступ до алгоритмів, 2019, с. 35.

Джерела ред.

Посилання ред.


Це незавершена стаття про алгоритми.
Ви можете допомогти проєкту, виправивши або дописавши її.
Ця стаття потребує додаткових посилань на джерела для поліпшення її перевірності. Будь ласка, допоможіть удосконалити цю статтю, додавши посилання на надійні (авторитетні) джерела. Зверніться на сторінку обговорення за поясненнями та допоможіть виправити недоліки.
Матеріал без джерел може бути піддано сумніву та вилучено. (грудень 2017)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Sortuvannya vklyuchennyam abo sortuvannya vstavlyannyam 1 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 Klas Algoritm sortuvannyaStruktura danih masivNajgirsha shvidkodiya O n2 Najkrasha shvidkodiya O n Serednya shvidkodiya O n2 Prostorova skladnist u najgirshomu vipadku O n O 1 Optimalnij Perevazhno 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 Zmist 1 Opis 2 Realizaciya 3 Div takozh 4 Primitki 5 Dzherela 6 PosilannyaOpis red Na 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 Realizaciya red Pascal 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 takozh red Spisok algoritmivPrimitki red Vstup do algoritmiv 2019 s 35 Dzherela red Kormen Tomas Lejzerson Charlz Rivest Ronald Stajn Kliford 2019 Rozdil 2 1 Sortuvannya vstavlyannyam Vstup do algoritmiv vid 3 K I S s 35 41 ISBN 978 617 684 239 2 Posilannya red Animated Sorting Algorithms Insertion Sort grafichna demonstraciya roboti algoritmu Category Insertion Sort LiteratePrograms prikladi realizaciyi algoritmu na riznih movah programuvannya InsertionSort Insertion Sort Demonstration Sorting Algorithms Demo Sortuvannya vklyuchennyam nbsp Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno gruden 2017 Otrimano z https uk wikipedia org w index php title Sortuvannya vklyuchennyam amp oldid 31996321