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

Remove ads
Опис
На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію у вже відсортованому списку доти, доки набір вхідних даних не буде вичерпано. Метод вибору чергового елементу з початкового масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються за порядком їх появи у вхідному масиві.
Remove ads
Реалізація
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");
}
Remove ads
Див. також
Примітки
Джерела
Посилання
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads