18_LinearSort
.pdf
Пример сортировки подсчѐтом (1)
Пусть исходный массив содержит 7 элементов:
Н.Новгород, 2009 г. |
Оптимизация ПО. |
11 |
|
Сортировки |
|
|
|
Пример сортировки подсчѐтом (2)
Пусть исходный массив содержит 7 элементов:
Посчитаем количество элементов в массиве:
―18‖ – 1 шт. ―31‖ – 1 шт. ―74‖ – 2 шт. ―89‖ – 1 шт. ―113‖ – 1 шт. ―217‖ – 1 шт.
Н.Новгород, 2009 г. |
Оптимизация ПО. |
12 |
|
Сортировки |
|
|
|
Пример сортировки подсчѐтом (3)
Количество элементов в массиве: ―18‖ – 1 шт.
―31‖ – 1 шт. ―74‖ – 2 шт. ―89‖ – 1 шт. ―113‖ – 1 шт. ―217‖ – 1 шт.
Запишем элементы в отсортированном порядке в соответствии с подсчитанным количеством элементов:
Н.Новгород, 2009 г. |
Оптимизация ПО. |
13 |
|
Сортировки |
|
|
|
Реализация сортировки подсчѐтом
Для более эффективного подсчѐта количества элементов введѐм следующее ограничение:
–сортируются однобайтовые числа, принимающие значения от 0 до 255.
Таким образом, для подсчѐта необходимо хранить 256 счѐтчиков.
Создадим вспомогательный массив из 256 элементов (например, unsigned int) и проинициализируем его нулями. Индекс элемента в этом массиве будет соответствовать тому числу, которое считается.
Н.Новгород, 2009 г. |
Оптимизация ПО. |
14 |
|
Сортировки |
|
|
|
Пример сортировки подсчѐтом
Рассмотрим предыдущий пример, содержащий 7 элементов
Выполним подсчѐт количества элементов исходного массива, используя вспомогательный массив
Далее просматриваем вспомогательный массив и записываем посчитанное количество элементов в выходной массив
Н.Новгород, 2009 г. |
Оптимизация ПО. |
15 |
|
Сортировки |
|
|
|
Сортировка подсчѐтом
Для сортировки массива, содержащего однобайтовый числа, в данном примере необходим вспомогательный массив размером 1 КБ.
Алгоритм сортировки состоит из следующих шагов:
–просмотр исходного массива и подсчѐт количества элементов в этом массиве (количество сохраняется во вспомогательном массиве);
–просмотр вспомогательного массива и запись элементов в отсортированном порядке.
Трудоѐмкость: O(n).
Н.Новгород, 2009 г. |
Оптимизация ПО. |
16 |
|
Сортировки |
|
|
|
Ограничения сортировки подсчѐтом
Тип элементов вспомогательного массива определяет максимальное количество элементов, которое можно будет отсортировать:
–если использовать тип ―unsigned int‖, то максимальное количество элементов составит 4 294 967 295;
–если использовать тип ―unsigned short int‖, то – 65535;
–если использовать тип ―unsigned char‖, то – 255.
Тип сортируемых данных (диапазон значений) определяет размер вспомогательного массива:
–если сортировать однобайтовый тип (signed/unsigned char), то размер вспомогательного массива составит 256 элементов (>= 256 байт);
–если сортировать двухбайтовый тип (signed/unsigned short int), то – 65536 элементов (>= 64 КБ);
–если сортировать чѐтырѐхбайтовый тип (signed/unsigned int), то – 4 294 967 296 элементов (>= 4 ГБ).
Н.Новгород, 2009 г. |
Оптимизация ПО. |
17 |
|
Сортировки |
|
|
|
Модификации сортировки подсчѐтом
Если известно, что в исходном массиве минимальный элемент равен ―Min‖, а максимальный – ―Max‖, то вспомогательного массив достаточно создавать размером ―Max-Min+1‖. Трудоѐмкость алгоритма останется линейной, т.к. поиск минимального и максимального элементов осуществляется за линейное время.
С помощью сортировки подсчѐтом можно сортировать знаковые типы. Например, при сортировки ―signed char‖, принимающего значения от -128 до 127, индексу ―0‖ во вспомогательном массиве будет соответствовать значение ―-128‖, индексу ―1‖ – ―-127‖,…,индексу 255 – ―127‖.
Н.Новгород, 2009 г. |
Оптимизация ПО. |
18 |
|
Сортировки |
|
|
|
2.2.
Поразрядная сортировка
Н.Новгород, 2009 г. |
Оптимизация ПО. |
19 |
|
Сортировки |
|
|
|
2.2.1.
Поразрядная нисходящая сортировка
Н.Новгород, 2009 г. |
Оптимизация ПО. |
20 |
|
Сортировки |
|
|
|