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

Сортировка подсчетом(countingsort) — специализированный алгоритм, который очень хорошо работает, если элементы данных — целые числа, значения которых находятся в относительно узком диапазоне. Этот алгоритм работает достаточно быстро, например, если значения находятся между 1 и 1000.

Сортировка подсчетом начинается с создания массива для подсчета числа элементов, имеющих определенное значение. Если значения находятся в диапазоне между min_valueиmax_value, алгоритм создает массивCountsс нижней границейmin_valueи верхней границейmax_value. Если используется массив из предыдущего прохода, необходимо обнулить значения его элементов. Если существует M значений элементов, массив содержит M записей, и время выполнения этого шага порядка O(M).

For i = min To max

Counts(List(i)) = Counts(List(i)) + 1

Next i

В конце концов, алгоритм обходит массив Counts, помещая соответствующее число элементов в отсортированный массив. Для каждого значенияiмеждуmin_valueиmax_value, он помещаетCounts(i)элементов со значениемiв массив. Так как этот шаг помещает по одной записи в каждую позицию в массиве, он требует порядка O(N) шагов.

new_index = min

For i = min_value To max_value

For j = 1 To Counts(i)

sorted_list(new_index) = i

new_index = new_index + 1

Next j

Next i

Алгоритм целиком требует порядка O(M)+O(N)+O(N)=O(M+N) шагов. Если M мало по сравнению с N, он выполняется очень быстро. Например, если M<N, то O(M+N)=O(N), что довольно быстро. Если N=100.000 и M=1000, то M+N=101.000, тогда какN*log(N)=1,6 миллиона. Шаги, выполняемые алгоритмом сортировки подсчетом, также относительно просты по сравнению с шагами быстрой сортировки. Все эти факты объединяются, обеспечивая вместе невероятно высокую скорость выполнения сортировки подсчетом.

С другой стороны, если M больше, чем O(N*log(N)), тогда O(M+N) будет больше, чем O(N*log(N)). В этом случае сортировка подсчетом может оказаться медленнее, чем алгоритмы со сложностью порядка O(N*log(N)), такие как быстрая сортировка. В одном из тестов быстрая сортировка 1000 элементов со значениями от 1 до 500.000 потребовал 0,054 сек, в то время как сортировка подсчетом потребовала 1,76 секунд.

Сортировка подсчетом опирается на тот факт, что значения данных — целые числа, поэтому этот алгоритм не может просто сортировать данные других типов. В VisualBasicнельзя создать массив с границами от AAA до ZZZ.

10. Блочная сортировка (Самостоятельно)

Как и сортировка подсчетом, блочная сортировка(bucketsort) не использует операций сравнения элементов. Этот алгоритм использует значения элементов для разбиения их на блоки, и затем рекурсивно сортирует полученные блоки. Когда блоки становятся достаточно малыми, алгоритм останавливается и использует более простой алгоритм типа сортировки выбором для завершения процесса.

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

Для деления списка на блоки, алгоритм предполагает, что значения данных распределены равномерно, и распределяет элементы по блокам равномерно. Например, предположим, что данные имеют значения в диапазоне от 1 до 100 и алгоритм использует 10 блоков. Алгоритм помещает элементы со значениями 1‑10 в первый блок, со значениями 11‑20 — во второй, и т.д.

Если элементы распределены равномерно, в каждый блок попадает примерно одинаковое число элементов. Если в списке N элементов, и алгоритм использует N блоков, в каждый блок попадает всего один или два элемента. Программа может отсортировать их за конечное число шагов, поэтому время выполнения алгоритма в целом порядка O(N).

На практике, распределение данных обычно не является равномерным. В некоторые блоки попадает больше элементов, в другие меньше. Тем не менее, если распределение в целом близко к равномерному, то в каждом из блоков окажется лишь небольшое число элементов.

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