Сортировка имени и сложности времени

Question

Я «изобрел» «новый» алгоритм сортировки.Ну, я понимаю, что не могу придумать что-то хорошее, поэтому я попытался найти его в википедии, но все алгоритмы сортировки, похоже, не мои.Итак, у меня есть три вопроса:

1. Как называется этот алгоритм?
2. Почему он отстой?(сложность наилучшего, среднего и наихудшего времени)
3. Можно ли сделать его еще лучше, используя эту идею?

Итак, идея моего алгоритма: если у нас есть массив, мы можемподсчитать количество отсортированных элементов, и если это число меньше половины длины, мы можем изменить массив, чтобы сделать его более отсортированным.И после этого мы можем отсортировать первую половину и вторую половину массива.В лучшем случае нам нужен только O (n) - если массив полностью отсортирован в хорошем или плохом направлении.У меня есть некоторые проблемы с оценкой средней и худшей сложности по времени.

Код на C #:

    public static void Reverse(int[] array, int begin, int end) {
        int length = end - begin;
        for (int i = 0; i < length / 2; i++)
            Algorithms.Swap(ref array[begin+i], ref array[begin + length - i - 1]);
    }
    public static bool ReverseIf(int[] array, int begin, int end) {
        int countSorted = 1;
        for (int i = begin + 1; i < end; i++)
            if (array[i - 1] <= array[i])
                countSorted++;

        int length = end - begin;
        if (countSorted <= length/2)
            Reverse(array, begin, end);

        if (countSorted == 1 || countSorted == (end - begin))
            return true;
        else
            return false;
    }
    public static void ReverseSort(int[] array, int begin, int end) {
        if (begin == end || begin == end + 1)
            return;
        // if we use if-operator (not while), then array {2,3,1} transforms in array {2,1,3} and algorithm stop
        while (!ReverseIf(array, begin, end)) {
            int pivot = begin + (end - begin) / 2;
            ReverseSort(array, begin, pivot + 1);
            ReverseSort(array, pivot, end);
        }
    }
    public static void ReverseSort(int[] array) {
        ReverseSort(array, 0, array.Length);
    }

PS: Извините за мой английский.

Answer 1

Наилучшим случаем является Theta (n), например, для отсортированного массива. Худший случай - тета (n ^ 2 log n).

Верхняя граница

Вторичные подзадачи имеют отсортированный массив, которому предшествует или следует произвольный элемент. Это O (n log n). Если перед этим мы выполняем O (n) работу, решаем вторичную подзадачу в первой половине, а затем во второй половине, а затем делаем O (n) больше работы - O (n log n). Если получилось, выполнить O (n), отсортировать уже отсортированную первую половину (O (n)), решить вторичную подзадачу во второй половине, выполнить O (n), решить вторичную подзадачу в первой половине, отсортировать вторая половина уже отсортирована (O (n)), работа O (n) - O (n log n).

Теперь, в общем случае, мы решаем две первичные подзадачи на двух половинах, а затем медленно обмениваемся элементами через свод, используя вторичные вызовы. Необходимы обмены O (n), поэтому прямое применение основной теоремы дает оценку O (n ^ 2 log n).

Нижняя граница

Для k> = 3 мы строим массив A (k) размером 2 ^ k рекурсивно, используя приведенный выше анализ в качестве руководства. Плохие случаи - это массивы [2 ^ k + 1] + A (k).

Пусть A (3) = [1, ..., 8]. Этот отсортированный базовый случай удерживает Reverse от вызова.

При k> 3 пусть A (k) = [2 ^ (k-1) + A (k-1) [1], ..., 2 ^ (k-1) + A (k-1) ) [2 ^ (k-1)]] + A (k-1). Обратите внимание, что основные подзадачи из [2 ^ k + 1] + A (k) эквивалентны [2 ^ (k-1) + 1] + A (k-1).

После первичных рекурсивных вызовов массив [2 ^ (k-1) + 1, ..., 2 ^ k, 1, ..., 2 ^ (k-1), 2 ^ k + 1 ]. Существуют элементы Omega (2 ^ k), которые должны перемещать позиции Omega (2 ^ k), и каждый из вторичных вызовов, которые перемещают элемент до сих пор, имеет подзадачи, отсортированные O (1), и, таким образом, является Omega (n log n).

---

Очевидно, что требуется больше кофе - первичные подзадачи не имеют значения. Это облегчает анализ среднего случая , который также равен Theta (n ^ 2 log n) .

С постоянной вероятностью, первая половина массива содержит, по крайней мере, половину наименее квартиля и, по крайней мере, половину наибольшего квартиля. В этом случае, независимо от того, происходит ли Reverse, существуют элементы Omega (n), которые должны перемещать позиции Omega (n) посредством вторичных вызовов.

Answer 2

Кажется, этот алгоритм, даже если он работает ужасно со «случайными» данными (как продемонстрировал Пер в их ответе), довольно эффективен для «исправления» массивов, которые «почти отсортированы».Таким образом, если бы вы решили развивать эту идею дальше (лично я бы не стал, но если бы вы хотели думать об этом как об упражнении), вам лучше было бы сосредоточиться на этой силе.

эта ссылкав Википедии в статье Inversion очень хорошо упоминается этот вопрос.Книга Махмуда довольно проницательна, поскольку отмечает, что существуют различные способы измерения «сортировки».Например, если мы используем число инверсий для характеристики «почти отсортированного массива», то мы можем использовать сортировку вставок, чтобы отсортировать ее очень быстро.Однако, если ваши массивы «почти отсортированы» по-разному (например, колода карт, которая вырезана или свободно перетасована), сортировка по вставке не будет лучшей сортировкой для «исправления» списка.

• Ввод: массив, который уже был отсортирован с размером N, с примерно N / k инверсиями.

Я мог бы сделать что-то подобное для алгоритма:

• Рассчитать количество инверсий.(O(N lg(lg(N))), или можно предположить, что он мал и пропустить шаг)
  • Если число инверсий <[порог], сортируйте массив, используя сортировку вставкой (это будет быстро). </li>
  • В противном случаемассив не близок к сортировке;прибегнуть к использованию вашего любимого алгоритма сортировки сравнения (или лучше)

Хотя есть и лучшие способы сделать это;такой «массив» можно «исправить» как минимум за O(log(N)*(# new elements)) времени, если вы достаточно предварительно обработаете свой массив или используете правильную структуру данных, например, массив со свойствами связанного списка или аналог, который поддерживает бинарный поиск.

Вы можете обобщить эту идею еще дальше.Будет ли работать «исправление» массива, зависит от того, какой тип исправления требуется.Таким образом, если вы обновляете эту статистику всякий раз, когда добавляете элемент в список или изменяете его, вы можете использовать хороший алгоритм «исправить это».

Но, к сожалению, все это будет болезненно для кода.Возможно, вам просто удастся сойти с нуля - приоритетная очередь .