сортировка Шелла

Also known as Shell sort, Shell's method, Shellsort, Shell sort, Shell's method

алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками

Key facts

Algorithm.class: Sorting algorithm
Algorithm.image: Step-by-step visualisation of Shellsort
Algorithm.caption: Shellsort with gaps 23, 10, 4, 1 in action
Algorithm.data: Array
Algorithm.time: O(n2) (worst known worst case gap sequence)O(n log2n) (best known worst case gap sequence)
Algorithm.best time: O(n log n) (most gap sequences)O(n log2n) (best known worst-case gap sequence)
Algorithm.average time: depends on gap sequence
Algorithm.space: О(n) total, O(1) auxiliary
Algorithm.optimal: No

via Wikipedia infobox

Wikidata facts

Image: Sorting shellsort anim.gif

Sources (3)

Article · Русский

Сортировка Шелла (англ. Shell sort) — алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

Abstract from DBpedia / Wikipedia · CC BY-SA