K-sort: новый алгоритм, превосходящий пирамидальную при n <= 7 000 000

От переводчика. Перевод статьи 2007 года на arxiv.org о статистическом анализе модификации быстрой сортировки.
Наверняка найдутся люди, использующие описанный вариант интуитивно. Здесь — математическое обоснование эффективности при n <= 7 000 000

Коротко о главном

Ключевые слова
Внутренняя сортировка; Равномерное распределение; Средняя временная сложность; Статистический анализ; Статистическая оценка

Сундараджан и Чакраборти [10] представили новую версию быстрой сортировки, удаляющую обмены. Крейзат [1] отметил, что алгоритм хорошо конкурирует с некоторыми другими версиями быстрой сортировки. Однако он использует вспомогательный массив, увеличивая пространственную сложность. Здесь мы предоставляем вторую версию, где мы удалили вспомогательный массив. Эта версия, называемая нами K-sort, упорядочивает элементы быстрее пирамидальной при значительном размера массива (n <= 7 000 000) для однородных (в статистическом смысле — прим. перев.) входных равномерного распределения U[0, 1].

1. Введение

Существует несколько методов внутренней сортировки (где все элементы могут храниться в основной памяти). Простейшие алгоритмы, такие как пузырьковая сортировка, обычно занимают время O (n²) упорядочивая n объектов и полезны только для малых множеств. Одним из самых популярных алгоритмов больших множеств является Quick sort, занимающий O(n*log₂n) в среднем и O (n²) в худшем случае. Подробно об алгоритмах сортировки читайте у Кнута [2].

Сундараджан и Чакраборти [10] представили новую версию быстрой сортировки, удаляющую обмены. Крейзат (Khreisat) [1] обнаружил, что этот алгоритм хорошо конкурирует с некоторыми другими версиями Quick sort, такими как SedgewickFast, Bsort и Singleton sort для n [3000..200 000]. Поскольку в алгоритме сравнения преобладают над обменами, удаление обменов не делает сложность этого алгоритма отличной от сложности классической быстрой сортировки. Другими словами, наш алгоритм имеет среднюю и худшую сложность, сравнимую с Quick sort, то есть O(n*log₂n) и O(n²) соответственно, что также подтверждается Крейзатом [1]. Однако он использует вспомогательный массив, тем самым увеличивая пространственную сложность. Здесь мы предлагаем вторую улучшенную версию нашей сортировки, которую мы называем K-sort, где удалён вспомогательный массив. Обнаружено, что сортировка элементов с K-sort выполняется быстрее пирамидальной при значительном размере массива (n <= 7 000 000) равномерно распределённых входных U[0, 1].

1.1 K-sort

Step-1: Инициализируйте первый элемента массива как key, i как left, j как (right+1), k = p когда p это (left+1).
Step-2: Повторяйте step-3 до выполнения условия (j-i) <= 2
Step-3: Сравните a[p] и key. Если key <= a[p]
то,

Step-4: установите a[i] = key
если (flag == 1) then
присвойте a[i+1] = temp
Step-5: если (left < i - 1), то
Отделите от основного вспомогательный массив, начиная с i-того и повторяйте шаги 1-4 со вспомогательным
Step-6: если (left > i + 1), то
Отделите от основного вспомогательный массив, начиная с i-того и повторяйте шаги 1-4 со вспомогательным


Демонстрация

Примечание. Если вспомогательный массив имеет одно значение, его не нужно обрабатывать.

2. Эмпирическая (средняя временная сложность)

Компьютерный эксперимент представляет собой серию прогонов кода для различных входов (см. Сакс [9]). Проводя компьютерные эксперименты на Borland International Turbo 'C ++' 5.02, мы могли бы сравнить среднее время сортировки в секундах (среднее значение приняло более 500 чтений) для разных значений n для K-sort и Heap. Используя симуляцию Монте-Карло (см. Кеннеди и Джентл [7]), массив размером n был заполнен независимыми непрерывными однородными U[0, 1] вариациями, и скопирован в другой массив. Эти массивы сортировались сравниваемыми алгоритмами. Таблица 1 и рис. 1 показывает эмпирические результаты.

Рис. 1 График сравнения

Наблюдаемые средние значения времени из непрерывного равномерного распределения U(0,1) для рассматриваемый сортировок представлены в таблице 1. Рисунок 1 вместе с таблицей 1 показывают сравнение алгоритмов.

Точки на графике, построенном из таблицы 1, показывают, что среднее время выполнения для K-сортировки меньше, чем у сортировки кучей, когда размер массива меньше или равен 7 000 000 элементов, а выше этого диапазона Heapsort выполняется быстрее.

3. Статистический анализ эмпирических результатов с использованием Minitab версии 15

3.1. Анализ для K-sort: регрессирование среднего времени сортировки y(K) по n*log 2 (n) и n

R обозначает наблюдение с большими стандартизованными остатками.
Рис. 2.1-2.4 показывает наглядный итог некоторых дополнительных испытаний модели.

4. Дискуссионная часть

Легко видеть, что сумма квадратов, внесенных n*log(n) в регрессионную модель как в сортировке K-sort, так и в Heap, существенна, по сравнению с суммой, полученной n. Напомним, что оба алгоритма имеют среднюю сложность O(n*log₂n). Таким образом, экспериментальные результаты подтверждают теорию. Мы сохранили n-член в модели, потому что взгляд на математический оператор, приводящий к сложности O(nlog₂n) в сортировке Quick sort и Heap, предполагает n-член (см. Кнута [2]).

Сравнительное уравнение регрессии для среднего случая получается просто путем вычитания y(H) из y(K).

Имеем, y(K) — y(H) = 0.52586 + 0.00000035 n*log2(n) – 0.00000792 n ……..(3)
Преимущество уравнений (1), (2) и (3) состоит в том, что мы можем прогнозировать среднее время выполнения обоих алгоритмов сортировки, а также их разность даже при огромных значениях n, громоздких для выполнения. Такое «дешевое предсказание» является девизом в компьютерных экспериментах и ​​позволяет нам проводить стохастическое моделирование даже для неслучайных данных. Другим преимуществом является то, что достаточно знать только размер ввода, чтобы сделать прогноз. То есть весь вход (для которого ответ фиксирован) не требуется. Таким образом, предсказание через стохастическую модель не только дешево, но и более эффективно (Сакс, [9]).

Важно отметить, что когда мы непосредственно работаем над временем выполнения программы, мы фактически рассчитываем статистическую оценку в конечном диапазоне (компьютерный эксперимент не может быть выполнен для ввода бесконечного размера). Статистическая оценка отличается от математической оценки в том смысле, что в отличие от математической она взвешивает, а не точно рассчитывает вычислительные операции и, как таковая, способна смешивать различные операции в концептуальную оценку, тогда как математическая сложность специфична для операции. Здесь время операции принимается за ее вес. Общее обсуждение статистической оценки, включающей формальное определение и другие свойства, см. Чакраборти и Соубик [5]. Смотрите также Чакраборти, Моди и Паниграхи [4], чтобы понимать, почему статистическая оценка является идеальной границей параллельных вычислений. Предположение о статистической оценке получается путем запуска компьютерных экспериментов, где весам присваиваются численные значения в конечном диапазоне. Это означает, что достоверность связанной оценки зависит от правильной разработки и анализа нашего компьютерного эксперимента. Связанную литературу по компьютерным экспериментам с другими областями применения, такими как проектирование СБИС, сжигание, теплопередача и т. Д., Можно найти в (Фанг, Ли и Суджианто, [3]). Смотрите также обзор (Чакраборти [6]).

5. Заключение и предложения для будущей работы

K-sort, очевидно, быстрее, чем Heap для количества элементов сортировки до 7 000 000, хотя оба алгоритма имеют одинаковый порядок сложности O(n*log₂n) в среднем случае. Будущая работа включает исследование параметризованной сложности (Mahmoud, [8]) по этой улучшенной версии. В качестве заключительного комментария мы настоятельно рекомендуем K-sort по крайней мере для n <= 7 000 000.
Тем не менее, мы соглашаемся выбрать Heap-sort в худшем случае из-за того, что он поддерживает сложность O (n*log₂n) даже в худшем случае, хотя программировать её сложнее.

N.B. Продолжение работы, 2012

Список литературы

[1] Khreisat, L., QuickSort A Historical Perspective and Empirical Study, International Journal of Computer Science and Network Security, VOL.7 No.12, December 2007, p. 54-65

[2] Knuth, D. E., The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison
Wesely (Pearson Education Reprint), 2000

[3] Fang, K. T., Li, R. and Sudjianto, A., Design and Modeling of Computer Experiments
Chapman and Hall, 2006

[4] S. Chakraborty, S., Modi, D. N. and Panigrahi, S., Will the Weight-based Statistical Bounds
Revolutionize the IT?, International Journal of Computational Cognition, Vol. 7(3), 2009, 16-22

[5] Chakraborty, S. and Sourabh, S. K., A Computer Experiment Oriented Approach to
Algorithmic Complexity, Lambert Academic Publishing, 2010

[6] Chakraborty, S. Review of the book Design and Modeling of Computer Experiments authored by K. T. Fang, R. Li and A. Sudjianto, Chapman and Hall, 2006, published in Computing Reviews, Feb 12, 2008,
www.reviews.com/widgets/reviewer.cfm?reviewer_id=123180&count=26

[7] Kennedy, W. and Gentle, J., Statistical Computing, Marcel Dekker Inc., 1980

[8] Mahmoud, H.,Sorting: A Distribution Theory, John Wiley and Sons, 2000

[9] Sacks, J., Weltch, W., Mitchel, T. and Wynn, H., Design and Analysis of Computer Experiments, Statistical Science 4 (4), 1989

[10] Sundararajan, K. K. and Chakraborty, S., A New Sorting Algorithm, Applied Math. and Compu., Vol. 188(1), 2007, p. 1037-1041

Автор: stranger777

Источник