ЛЕКЦИЯ 3. СОРТИРОВКИ ПОДСЧЁТОМ. СОРТИРОВКА РАЗДЕЛЕНИЕМ.
Цель лекции: изучить методы сортировки подсчётом, сортировки разделением(быстрая сортировка Хоара).
Рассматриваемые вопросы: сортировка простым подсчётом, алгоритм сортировки подсчётом со списком, сортировка разделением.
Сортировка подсчётом
Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать. Необходимость сортировки внутри ячеек лишает алгоритм смысла, так как каждый элемент придётся просматривать более одного раза.
Предположим, что входной массив состоит из n целых чисел в диапазоне от 0 до k − 1, где 
. Существует несколько модификаций сортировки подсчётом, ниже рассмотрены три линейных и одна квадратичная.
Простой алгоритм подсчетом.Это простейший вариант алгоритма. Создать вспомогательный массив C[0..k - 1], состоящий из нулей, затем последовательно прочитать элементы входного массива A, для каждого A[i] увеличить C[A[i]] на единицу. Теперь достаточно пройти по массиву C, для каждого 
в массив A последовательно записать число j C[j] раз.
|
|
|
Пусть имееются числа из диапазона от 0 до 9.
| Начальное состояние массива А | 1 5 2 7 2 3 7 |
| Начальное состояние массива С | 0 0 0 0 0 0 0 0 0 0 |
| Шаг 1 массив С | 0 1 2 1 0 1 0 2 0 0 |
| Шаг 2 массив А | 1 2 2 3 5 7 7 |
Алгоритм со списком.Этот вариант используется, когда на вход подается массив структур данных, который следует отсортировать по ключам (key). Нужно создать вспомогательный массив C[0..k - 1], каждый C[i] в дальнейшем будет содержать список элементов из входного массива. Затем последовательно прочитать элементы входного массива A, каждый A[i] добавить в список C[A[i].key]. В заключении пройти по массиву C, для каждого в массив A последовательно записывать элементы списка C[j]. Алгоритм устойчив.
Алгоритма имеют линейную временную трудоёмкость О(n + k).
Квадратичный алгоритм сортировки подсчётом
Также сортировкой подсчётом называют немного другой алгоритм. В нём используются входной массив A , вспомогательный массив B для отсортированного множества, . вспомогательный массив С. В алгоритме следует для каждого элемента входного массива A[i] подсчитать количество элементов меньших него c1 и количество элементов, равных ему, но стоящих ранее c2 (c = c1 + c2). B[c] присвоить A[i]. Алгоритм устойчив.
|
|
|
| Начальное состояние массива А[0..6] | 1 5 2 7 2 3 7 |
| Начальное состояние массива С[0..6] | 0 0 0 0 0 0 0 |
| Конечное состояние массива С[0..6] | 0 4 1 5 2 3 6 |
| Начальное состояние массива А[0..6] | 0 0 0 0 0 0 0 |
| B[C[0]]=A[0] | 1 0 0 0 0 0 0 |
| B[C[4]]=A[1] | 1 0 0 0 5 0 0 |
| B[C[1]]=A[2] ‘ | 1 2 0 0 5 0 0 |
| B[C[5]]=A[3] | 1 2 0 0 5 7 0 |
| B[C[2]]=A[4] | 1 2 2 0 5 7 0 |
| B[C[3]]=A[5] | 1 2 2 3 5 7 0 |
| B[C[6]]=A[6] | 1 2 2 3 5 7 7 |
| Отсортированный массив В[0..6] | 1 2 2 3 5 7 7 |
Сложность метода О(n2)
Дата добавления: 2018-05-02; просмотров: 672; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!