алгоритм — реализация последовательности сортировки оболочки в переполнении стека
Я читаю о сортировке оболочки в алгоритмах на С ++ Роберта Седвика.
Здесь внешний цикл для изменения приращений приводит к этой компактной реализации сортировки оболочек, которая использует последовательность приращений 1 4 13 40 121 364 1093 3280 9841. , , ,
template <class Item>
void shellsort(Item a[], int l, int r)
{
int h;
for (h = 1; h <= (r - l) / 9; h = 3 * h + 1);
for (; h > 0; h = h / 3)
{
for (int i = l + h; i <= r; i++)
{
int j = i; Item v = a[i];
while (j >= l + h && v < a[j - h])
{
a[j] = a[j - h]; j -= h;
}
a[j] = v;
}
}
}
Мой вопрос, на каком основании автор проверяет условие h <= (r-l) / 9, и почему автор делит на 9.
Решение
Петля:
for (h = 1; h <= (r - l) / 9; h = 3 * h + 1);
рассчитывает начальное значение h, Это значение должно быть меньше диапазона, в котором оно будет использоваться:
h <= (r - l)
Каждый раз, когда это условие проходит, h обновляется до 3 * h + 1Это означает, что даже если h меньше чем (r-l)обновленное значение может быть больше. Чтобы предотвратить это, мы могли бы проверить, если следующее значение h превзойдет самый большой показатель:
(h * 3) + 1 <= (r - l)
Это обязательно h меньше, чем диапазон массива.
Например: скажем, у нас есть массив размером 42, что означает, что индексы идут от 0 до 41. Используя условие, как описано выше:
h = 1, is (3 * 1 + 1) <= (41 - 0) ? yes! -> update h to 4
h = 4, is (3 * 4 + 1) <= (41 - 0) ? yes! -> update h to 13
h = 13, is (3 * 13 + 1) <= (41 - 0) ? yes! -> update h to 40
h = 40, is (3 * 40 + 1) <= (41 - 0) ? no! => h will begin at 40
Это означает, что наш начальный h 40, потому что h только немного меньше, чем диапазон массива, очень мало работы будет сделано, алгоритм будет только проверять следующее:
- Нужно ли менять массив [40] на массив [0]?
- Нужно ли менять массив [41] на массив [1]?
Это немного бесполезно, первая итерация выполняет только две проверки. Меньшее начальное значение h означает, что в первой итерации будет выполнено больше работы.
С помощью:
h <= (r - l) / 9
обеспечивает начальную стоимость h быть достаточно маленьким, чтобы первая итерация могла выполнять полезную работу. Как дополнительное преимущество, он также выглядит чище, чем предыдущее условие.
Вы можете заменить 9 на любое значение больше 3. Почему больше 3? Для обеспечения (h * 3) + 1 <= (r - l) все еще правда!
Но не забудьте не сделать начальный h Слишком маленький: Shell Sort основан на Insertion Sort, который хорошо работает только с маленькими или почти отсортированными массивами. Лично я бы не превысил h <= (r - l) / 15,
Другие решения