Помогая ученику с его классами, я внедрил двойной алгоритм быстрой сортировки, чтобы подготовить сеанс и заинтриговать. После запуска некоторых статистических данных, затем решения ситуации с наихудшим случаем, затем повторного запуска статистики и повторного решения следующей ситуации в худшем случае и повторения этого процесса несколько раз, полученный код не более 80 строк простого простого кода Python (бит меньше кода Владимира). Новая часть состоит в том, как три раздела построены в сочетании с очень простой, но эффективной постобработкой. Теперь мне нужна помощь в том, как правильно тестировать и делать статистику.Подсчет свопов для сортировки статистики - что с свопами с двумя заданиями вместо трех
Особенно о том, как подсчитать свопы: большинство свопов выполняют только два задания вместо трех. Поэтому я должен считать их полными свопами или, справедливо ли считать их только как «2/3» обмен?
Подсчет каждый свопа, как 1, то Cn в Cn * N * log2(N) составляет около 0.48 на короткие списки (< 100 элементов) и вокруг 0.55 на более длинных списках нескольких миллионов элементов. Это только теоретический минимум , рассчитанный на Владимир Ярославский.
Counting легких свопов как 2/3 вместо этого, количества необходимых свопов практически одинаков для любого размера списка и составляет около 0.36 (STDEV вокруг 0.015).
Cn для числа сравнений в среднем около 1.3 для списков 2 миллиона записей, что составляет менее чем теоретическое 1,38 (от 2 * N * Ln (N)), и ниже для более коротких списков, т.е. 1024 элементов, это около 1.21
то есть для списков с 100% уникальных номеров и случайным образом упорядоченных с Питона random.shuffle().
Так что мой вопрос:
нормально ли это считать легкие свопы как таковой, и является результатом действительно многообещающим или нет?
Также интересен:
- более одинаковых элементов в списке, тем быстрее сорта.
Cn-0.03и0.1для свопов и сравнений соответственно для 2 миллиона список всех равные элементы. Cnдля отсортирован и обратных упорядоченных списков почти одинаковы для всех размеров:0.3и1для свопа (подсчитанный с2/3) и сравнением соответственно.
Я отправлю список с более подробной статистикой, которая включает в себя максимальную глубину стека, количество рекурсивных вызовов помимо свопов и сравнений. Есть ли еще другие вещи?
Также существуют некоторые «стандартные» тестовые комплекты с файлами всех видов ситуаций (с равными, частично отсортированными и т. Д.), Которые можно использовать для тестирования алгоритма сортировки и для сопоставления результатов с другими алгоритмами сортировки.
Добавлено 5 мая: я улучшил алгоритм специально для отсортированных списков. Ниже приведены результаты для 20 прогонов для каждого. Хорошие ли результаты?
New statistics:
Random.shuffle(), unique number
Length Swaps/Nlog2(N) Comparisons/Nlog2(N) Maximum Stack/log2(N)
16 0.367 0.922 0.250
64 0.360 1.072 0.500
256 0.342 1.122 0.625
1024 0.358 1.156 0.800
4096 0.359 1.199 0.917
16384 0.359 1.244 1.071
65536 0.360 1.244 1.125
262144 0.360 1.269 1.167
1048576 0.362 1.275 1.200
Sorted, unique numbers
Length Swaps/Nlog2(N) Comparisons/Nlog2(N) Maximum Stack/log2(N)
16 0.172 0.531 0.250
64 0.117 0.586 0.333
256 0.087 0.609 0.375
1024 0.075 0.740 0.500
4096 0.060 0.732 0.500
16384 0.051 0.726 0.500
65536 0.044 0.722 0.500
262144 0.041 0.781 0.556
1048576 0.036 0.774 0.550
2097152 0.035 0.780 0.571
Reversed order, unique numbers
Length Swaps/Nlog2(N) Comparisons/Nlog2(N) Maximum Stack/log2(N)
16 0.344 0.828 0.250
64 0.279 0.812 0.333
256 0.234 0.788 0.375
1024 0.210 0.858 0.500
4096 0.190 0.865 0.500
16384 0.172 0.855 0.500
65536 0.158 0.846 0.500
262144 0.153 0.900 0.556
1048576 0.143 0.892 0.550
2097152 0.140 0.895 0.571
Как мы можем поменять местами два числа с двумя заданиями? – Sayakiss
@Sayakiss При сортировке перенос записи в нужное место не всегда требует обмена с другим значением. Хорошим примером является перемещение позиции списка 1, не нужно менять каждый элемент. –