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

Ответ от Анатолий[гуру]
Что ж тут непонятного?
Давай сначала по-простому? :-))
- алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками.
Какое ключевое слово здесь? Правильно - вставками. Плохо вставишь - не отсортируется ведь!
Читаем дальше:
"...Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской...."
Теперь какое ключевое слово было? Правильно - грубыми проходами!! !Иногда бывает так, что, типа, ласка, нежность, но.. иногда ведь хочется и грубости?...Так.. я отвлекся.. .
Читаем дальше:
"...При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше) .
Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:
* отсутствие потребности в памяти под стек;
* отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла...."
Вот и всё....Практически понятно.. 🙂
Ну, и для закрепления - посмотрим наглядно: :-))