По поводу алгоритма сортировки оболочки

Question

Я читаю abook на алгоритмах. Это упоминается в сортировке оболочки, как показано ниже

Важное свойство Shellsort (которое мы заявляем без доказательств) что (h subscipt k) hk-отсортированный файл, который затем (h subsciprt (k-1)) сортировка по hk-1 остается сортировка по hk. Если бы это было не так, то Алгоритм, скорее всего, не будет иметь большого значения, поскольку этапы будут отменены на более поздних этапах.

Мой вопрос: что автор подразумевает под приведенным выше утверждением?

Спасибо!

Answer 1

Shell sort - алгоритм многопроходной сортировки. Он работает путем сортировки подмножества массива по определенному целочисленному значению "шага" k, т. Е. Доступ только к каждому kth элементу в массиве.

Изначально используется большое значение шага, при последующих проходах это значение шага уменьшается до тех пор, пока не будет выполнен последний проход с шагом 1 (который обычно является просто стандартной фазой сортировки вставки), и массив полностью отсортированный.

Заявление, о котором вы спрашивали, просто говорит о том, что любая сортировка, выполненная на более ранних проходах (большие значения шага), сохраняется на более поздних проходах (меньшие значения шага). Если бы это было не так, не было бы смысла в многопроходном подходе, используемом сортировкой оболочки.

Надеюсь, это поможет.