сортировка вставками

алгоритм сортировки, в котором каждый следующий входящий элемент помещается в подходящее место среди ранее упорядоченных элементов

Key facts

Class: Sorting algorithm
Data structure: Array
Worst case performance: O ( n 2 ) {\displaystyle O(n^{2})} comparisons and swaps
Best case performance: O ( n ) {\displaystyle O(n)} comparisons, O ( 1 ) {\displaystyle O(1)} swaps
Average performance: O ( n 2 ) {\displaystyle O(n^{2})} comparisons and swaps
Worst case space complexity: O ( n ) {\displaystyle O(n)} total, O ( 1 ) {\displaystyle O(1)} auxiliary
Optimal: No

via Wikipedia infobox

Wikidata facts

Instance of: online algorithm
Image: Insertion sort.gif

Show 4 more facts

Commons category: Insertion sort
name in kana: インサーションソート
Stack Exchange tag: stackoverflow.com/tags/insertion-sort
derivative work: Timsort

Sources (2)

via Wikidata · CC0

Article · Русский

Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов. Вычислительная сложность — .

Abstract from DBpedia / Wikipedia · CC BY-SA