По какой формуле вычисляется количество проходов при сортировке оболочки?

Question

Я имею в виду оригинальный алгоритм (алгоритм Дональда Шелла). Я пытаюсь сделать субъективную сортировку на основе сортировки оболочки. Я уже сделал все logi c, где он точно такой же, как сортировка оболочки, но вместо того, чтобы компьютер вычислять, что больше, пользователь субъективно определяет, что больше. Но я хотел бы показать процент или что-то, чтобы пользователь знал, как далеко он уже находится в сортировке. Вот почему я хочу найти способ узнать это.

Какова формула для получения количества проходов при сортировке оболочки? Я заметил, что число не фиксировано, так что будет минимум и максимум? N и N ^ 2? Или, может быть, если у вас есть представление о том, как лучше всего отображать прогресс сортировки, я буду очень признателен.

PS: Дело не в количестве сравнений! И не о временной сложности. У меня вопрос о количестве проходов в массиве.

Я сделал эту формулу, отображая ее по цвету. Но это не работает с правильным диапазоном.

List<Color> colors = [
    Color(0xFFFF0000),//red
    Color(0xFFFF5500),
    Color(0xFFFFAA00),
    Color(0xFFFFFF00),//yellow
    Color(0xFFAAFF00),
    Color(0xFF00FF00),
    Color(0xFF00FF00),//green
  ];
[...]
style: TextStyle(
                          color: colors[(((pass - 1) * (colors.length - 1)) /
                                  sqrt(a.length).ceil())
                              .floor()]),
[...]

Answer 1

Поскольку один проход представляет собой применение одного элемента последовательности пропусков, количество проходов зависит от используемой последовательности пропусков.

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

Вы можете узнать больше о других предлагаемых последовательностях пропусков в статье в Википедии о Сортировке оболочки: https://en.wikipedia.org/wiki/Shellsort