CodeLAB
на главную карта сайта обратная связь

Популярные задачи:

#Создание нестандартного (custom-ного) окна браузера. (35852 hits)
#Код. (179588 hits)
#Динамическое формирование выпадающего списка. (51789 hits)
#Обработка шаблонных писем. (51906 hits)
#Посчитать количество пар чисел (number of equal pairs). (4541 hits)
#"C# и платформа .NET" Эндрю Троелсен (Andrew Troelsen, "C# and the .NET platform"), листинги, код, примеры из книги, исходники. (38810 hits)
#Постепенное затемнение. (51277 hits)
#Интерактивная, динамическая подгрузка картинок. (69738 hits)
#Последовательный поиск и его оптимизации. (44715 hits)
#Вычисление среднего, среднего отклонения, среднеквадратического отклонения и дисперсии заданной выборки. (46352 hits)
#Преобразование RGB в HEX и обратно HEX в RGB. (56665 hits)
#Простой генератор случайных чисел. (133855 hits)
#Улучшение быстрой сортировки. (76785 hits)
#Пирамидальная сортировка. (203455 hits)
#qForms, библиотека типичного функционала валидации/построения/связки html-форм. (147171 hits)
#Часики на js. (92618 hits)
#Рисование множества Мандельброта. (44257 hits)
#Глубокое полное клонирование. (35725 hits)
#Вычисление значения полинома. (62023 hits)
#Вставка новой записи в таблицу БД. (36501 hits)


Главная >> Каталог задач >> Сортировка >> Поразрядная Сортировка >> Поразрядная сортировка массива подсчетом

Поразрядная сортировка массива подсчетом

Aвтор:
Дата:
Просмотров: 133028
реализации(C++: 2шт...) +добавить

[Если вы еще не знакомы с поразрядной сортировкой как таковой, то быстрей прочитайте задачу поразрядная сортировка, общий принцип]

Формулировка

В классической поразрядной сортировке на каждом проходе, т.е. в пределах каждого разряда - элементы сортировались путем буквального разделения по каждому разряду, т.е. мы получали последовательности элементов, в каждой из которых содержались т.н. "одинаковые" элементы (идиентичны по конкретному текущему разряду). Очевидно, что для того, чтобы получить единую последовательность элементов отсортированных в пределах одного этого разряда - надо просто один за другой, по-порядку соединить все эти последовательности между собой.

Подход, о котором идет речь здесь - отличается тем, что на каждом проходе элементы исходной последовательности сортируются по конкретному текущему разряду не с помощью разделения по карманам, а с помощью подсчета элементов, которые меньше индекса некоторого дополнительного массива счетчиков. Т.е. никаких уже 2 этапов: распределения и сборки. Теперь можно сказать - только подсчет и вставка элементов в нужное место.

Подробнее. Те же основные итерации по каждому разряду максимально-разрядного числа, от младшего к старшему разряду. В пределах каждой итерации - составляем последовательность(назовем ее positions) из значений разрядов каждого элемента нашей последовательности, чтобы только с этими значениями на данной итерации и работать (сами числа нам не нужны конечно - только текущие их разряды). Далее составляем искомый массив счетчиков - count, размером range. Каждое его значение будет определять количество элементов из positions, которые меньше индекса данного элемента массива count. После того, как такой массив будет составлен - мы будем знать где на самом деле на данной итерации должен находится каждый элемент из positions, чтобы последний был отсортирован, поскольку для каждого элемента positions мы знаем количество элементов меньших чем он и поэтому встравляем его на соответствующее место.

Пример.
Пусть имеем исходную последовательность из 10-ти элементов source = {3, 1, 3, 9, 1, 4, 3, 2, 8, 3}.
Т.о. range = 10, width = 1, n = 10.
Составляем массив count размера range, т.е. в данном случае - 10. Пока инициируем его нулями. Далее проходимся по source от начала и до конца и для каждого его значения - просто увеличиваем(инкрементируем) соответствующий элемент count, что-то вроде:

for i = 0 to n-1
count[ source[i] ]++

Получаем: count = {0 2 1 4 1 0 0 0 1 1}

Далее проходимся по count и для каждого элемента считаем сумму предыдущих:

count[i] = count[0] + count[1] + ... + count[i-1]

В нашем случае получим: count = {0 0 2 3 7 8 8 8 8 9} Т.е. каждый count[i] - это количество элементов, меньших i. Это и является ключом метода. Теперь мы проходимся по всем source[i] и зная количество элементов меньших source[i]: count[ source[i] ](=K например) - просто вставляем source[i] на следующую позицию: K+1.

На этом, по-сути, сортировка для данного примера и заканчивается, т.е. имеем здесь только одну главную итерацию алгоритма, т.к. максимальное количество разрядов(width) = 1. Если бы в исходном массиве были бы двухзначные числа(56, 35), то имел бы место еще один проход, который бы отличался только тем, что на нем рассматривался бы еще и второй, более старший разряд элементов(ключей).

 псевдокод: поразрядная сортировка подсчетом, общий алгоритм  ссылка
  1. // Наш исходный сортируемый массив
  2. x = {..<int> elements to be sorted...}
  3.  
  4. // Вспомогательная переменная
  5. rangepow = 1
  6.  
  7. // Вспомогательный массив,
  8. // копирующий исходный X
  9. source = array<int>[n] filled 0
  10.  
  11. for step = 0 to width-1
  12.  
  13. // массив подсчета
  14. count = array<int>[range] filled 0
  15.  
  16. // Копируем в source содержимое X
  17. // на текущей итерации
  18. source[] = copy of x[]
  19.  
  20. // Получаем в count пока просто
  21. // количества текущих разрядов
  22. for i = 0 to n-1
  23. // d - это значение текущего разряда
  24. // для каждого нашего числа
  25. d = (source[i] / rangepow) % range
  26. count[ d ]++
  27.  
  28. // Завершаем формирование count, т.е. получаем
  29. // количество элементов менших индекса
  30. summNum = 0 // вспомогательная переменная
  31. for i = 0 to range-1
  32. tmp = count[i]
  33. count[i] = summNum
  34. summNum += tmp
  35.  
  36.  
  37. // Завершающий этап "вставка"
  38. for i = 0 to n-1
  39. d = (source[i] / rangepow) % range;
  40. x[ count[d] ] = source[i];
  41. count[d]++; // Очень важная конструкция:
  42. // для случая посторяющихся чисел.
  43. }
  44. rangepow *= range
  45.  


Т.о. получаем, скорость ~ О(width*(2n + range)), память: ~(2n + range).

Оптимизация

Формирование ключевых массивов count можно начать заранее. Т.е. до запуска алгоритма, пробежавшись по нашему исходному массиву x - можно "наполовину" рассчитать все массивы count для каждого разряда, потому что неважно как расположены числа: количество одинаковых чисел по разрядам не меняется на каждом проходе. Поэтому если до основного цикла рассчитать все эти массивы count - на каждом проходе будет делаться лишь (n + range) операций, а не (2*n + range):

 псевдокод: поразрядная сортировка подсчетом, оптимизация  ссылка
  1. // Наш исходный сортируемый массив
  2. x = {..<int> elements to be sorted...}
  3.  
  4. // Вспомогательный массив,
  5. // копирующий исходный X
  6. source = array<int>[n] filled 0
  7.  
  8. // инициируем count пока нулями
  9. // и кстати - теперь он двухмерный!
  10. count = array<int>[width][n] filled 0
  11.  
  12. // рассчитываем количество чисел с
  13. // одинаковыми разрядами для всех значений
  14. // разрядов
  15. for i = 0 to n-1
  16. rangepow = 1
  17. for step = 0 to width-1
  18. d = (x[i] / rangepow) % range
  19. count[step][ d ]++;
  20.  
  21. // Вспомогательная переменная
  22. rangepow = 1
  23.  
  24. for step = 0 to width-1
  25.  
  26. // Копируем в source содержимое X
  27. // на текущей итерации
  28. source[] = copy of x[]
  29.  
  30. // Завершаем формирование count, т.е. получаем
  31. // количество элементов менших индекса
  32. summNum = 0 // вспомогательная переменная
  33. for i = 0 to range-1
  34. tmp = count[step][i]
  35. count[step][i] = summNum
  36. summNum += tmp
  37.  
  38.  
  39. // Завершающий этап "вставка"
  40. for i = 0 to n-1
  41. d = (source[i] / rangepow) % range
  42. x[ count[step][d] ] = source[i]
  43. count[step][d]++ // Очень важная конструкция:
  44. // для случая посторяющихся чисел.
  45. }
  46. rangepow *= range
  47.  


Т.о. получаем, сокращение скорости до: ~ O((width + 1)*(n + range)), но увеличение памяти до: ~(2n + width*range). Глядя на эту новую пропорцию скорости - выигрышь в производительности представляется не очень очевидным, но чисто логически рассуждая можно прийти к выводу, что общее количество проходов по исходному массиву x размера n - сокращается: с ~ 2*width*n, до (width + 1)*n.

Сравнительные диаграммы

Представляя на графиках производительности обеих алгоритмов(Graph1) и их отношение(т.е. насколько оптимизированная версия быстрее, Graph2) в зависимости от размера массива - n (при width=2, range=10), получим:

Как видим, наибольший выигрышь в скорости достигается на больших размерностях массива(>200). На малых же размерностях данная версия менее производительна(Graph3):

Точка перелома(n=10 в данном случае) очевидно определяется значениями width и range.

Что же касается увеличения расхода памяти, то при тех же условиях получим:

Т.е. на некоторую постоянную величину(определяющуюся значениями width и range) памяти будет расходоваться больше.

Реализации:

C++(2)   +добавить

1) неоптимизированная версия на C++, code #10[автор:this]
2) оптимизированная версия на C++, code #11[автор:this]