В копилку экзотических способов сортировки предложу еще один, немного своеобразный, но обещающий приличную скорость при хорошо случайных данных.
Пусть имеется набор N из n целых положительных чисел от 1 до n.
Самоочевидно, что для хранения n чисел необходимо иметь n ячеек. Вне зависимости от порядка, в котором числа будут записаны.
Исходный массив
| 3 | 5 | 2 | 1 | 8 | 4 | 7 | 6 | 9 | 10 |
Несложно представить, что неупорядоченный набор N достаточно просто заменить упорядоченным (по возрастанию, или по убыванию), записав упорядоченный набор на место неупорядоченного.
Упорядоченный массив
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Таким же образом можно «сортировать» наборы чисел (ограничимся целыми положительными), удовлетворяющие условию nmax-nmin = n.
Рассмотрим более сложный случай.
Пусть набор N (опять же целых положительных чисел) таков, что nmax-nmin > n, и все числа n(i) в наборе разные.
| 30 | 55 | 21 | 17 | 82 | 46 | 79 | 63 | 94 | 108 |
Чтобы отсортировать данный набор, нужно:
1) найти nmax , nmin
2) вычислить дельта d=(nmax-nmin) /n
3) для каждого n(i) (следующую процедуру назовем условно «разбрасыванием камней»):
3а) вычислить индекс indx=( n(i)-nmin)/d+1(так как вычисления также предполагаются в целых числах, единица добавляется для компенсации округления и исключения нулевого индекса)
Числа n(i) и индексы indx ака места, на которых должны стоять эти числа.
| 30 | 55 | 21 | 17 | 82 | 46 | 79 | 63 | 94 | 108 |
| 2 | 5 | 1 | 1 | 7 | 4 | 7 | 5 | 9 | 10 |
3б) в заранее подготовленном, заполненном нулями массиве «индексы» Indxs инкрементируем ячейку с индексом, полученным в предыдущем шаге
| 2 | 1 | 0 | 1 | 2 | 0 | 2 | 0 | 1 | 1 |
3в) считываем получившееся значение
3г) умножаем его на n и складываем с индексом, записываем по этому адресу число n(i) в массиве Nnew
Если попадаются одинаковые индексы, n(i) в массив N new записываем не рядом, а снизу.
| 21 | 30 | 46 | 55 | 82 | 94 | 108 | |||
| 17 | 63 | 79 |
4) далее приступаем к «сбору камней»
Кладем i=1 и последовательно считываем массив индексов Indxs пока i ≤ n
4а) если Indxs(i) = 0, переходим к следующему i
4б) если Indxs(i) = 1, считываем число из массива Nnew , выводим его в отсортированный массив, переходим к следующему i
4в) если Indxs(i) = 2, считываем числа из Nnew записанные «по-вертикали», сравниваем их и выводим сперва меньшее, затем большее, переходим к следующему i
4г) если Indxs(i) = 3, считываем 3 числа, находим среди них минимальное, выводим его и исключаем из списка, затем сравниваем два оставшихся и выводим уже их.
4д) для Indxs(i) = 4, все то же, сначала находим минимальное из четырех, вычеркиваем его, затем делаем тоже что и для индекса 3.
4е) если Indxs(i) больше 4, вызываем алгоритм рекурсивно.
Отсортированный массив
| 17 | 21 | 30 | 46 | 55 | 63 | 79 | 82 | 94 | 108 |
Попробуем оценить количество операций.
На поиск минимального и максимального нужен один проход — n операций.
На «разбрасывание камней» еще n операций.
«Сбор камней» по затратам зависит от входных данных. В данном случае нужно n копирований и 3 операции сравнения пары чисел.
При тестировании на наборах с n=10000, полученных с random.org (ресурс не дает больше 10000 чисел в одном наборе) алгоритм показывает следующую статистику:
При nmax =10000. Все индексы = 1, сортировка производится за 3 прохода по массиву.
При nmax =11000. Нулей почти половина: 4547, единиц 906, двоек :4547, троек и более:0 Те же три прохода плюс почти половина от n сравнений 2-х чисел.
При nmax =21000 Zeroes:3967 Ones:2845 Twos:2409 Threes:779 Fours:0
При nmax =31000 Zeroes:3881 Ones:3134 Twos:2197 Threes:680 Fours:108 More_than_four:0
При nmax =101000 max in index:6 Zeroes:3729 Ones:3541 Twos:1923 Threes:643 Fours:139 More_than_four:25
всего 25 вызовов второй итерации.
Интуитивно, в самом худшем случае будет совершено n/5 итераций.
В среднем, навскидку, число операций порядка 4n
Этот способ сортировки относится к группе сортировок без сравнений и является промежуточной версией между карманной и сортировкой с подсчетом.
Главная проблема сортировки подсчетом — необходимость дополнительно сортировать значения, попадающие в одну ячейку, имеет значимость при количестве чисел в ячейке больше 4-х.
Но, во-первых, мы имеем хороший гандикап за счет единиц и пар чисел.
Во-вторых, число бурстов обычно относительно невелико, менее одного процента.
В-третьих, уже на второй итерации бурсты очень хорошо отрабатываются. К тому же автоматически снимается ограничение на отсутствие повторов во входных данных. Если нам попадается бурст из одинаковых значений, то для него дельта d=(nmax-nmin) /n=0 и мы можем смело весь бурст скопировать на выход.
Проблема применимости этого способа сортировки не только для целых положительных чисел тоже вполне решаема.
Безусловно, данный способ требует большей обкатки и выявления подводных камней.
Преимущества:
Скорость, легкость понимания и программирования.
Недостатки:
Довольно большие требования к памяти, зависящие от входных данных. Что можно попытаться скомпенсировать более рациональной организацией массива Nnew . В любом случае памяти нужно не менее 3n.
This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.
Комментариев нет:
Отправить комментарий