Сортировка подсчетом сложных объектов — различия между версиями
Smolcoder (обсуждение | вклад) |
Smolcoder (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | ==Постановка задачи== | ||
Иногда надо отсортировать набор каких либо "сложных" данных, например, структур, в которых несколько полей, и сортировать надо по одному из них. | Иногда надо отсортировать набор каких либо "сложных" данных, например, структур, в которых несколько полей, и сортировать надо по одному из них. | ||
В данном случае для [[Сортировка подсчетом|сортировки подсчетом]] предполагается, что величины, хранящиеся в данных ключах, являются целыми числами от 0 до k - 1. | В данном случае для [[Сортировка подсчетом|сортировки подсчетом]] предполагается, что величины, хранящиеся в данных ключах, являются целыми числами от 0 до k - 1. | ||
| Строка 4: | Строка 5: | ||
Мы будем использовать все тот же алгоритм, что и для обыкновенных целых чисел, но с небольшой модификацией. Она необходима для разрешения следующей проблемы: разные структуры могут иметь одинаковые ключи. Нам надо каким-либо образом это учитывать. | Мы будем использовать все тот же алгоритм, что и для обыкновенных целых чисел, но с небольшой модификацией. Она необходима для разрешения следующей проблемы: разные структуры могут иметь одинаковые ключи. Нам надо каким-либо образом это учитывать. | ||
| + | == Решение == | ||
Пусть далее исходня последовательность из n структур хранится в массиве С, а отсортированная - в А, причем ее ключи прина | Пусть далее исходня последовательность из n структур хранится в массиве С, а отсортированная - в А, причем ее ключи прина | ||
Как можно модифицировать алгоритм? Например, сделать изкаждой ячейки массива А список, в который будем добавлять структуры с одинаковыми ключами. Однако, этот вариант плох тем, что надо поддерживать сам список, что не является самым простым решением. К тому же нам надо будет хранить дополнительную информацию в виде ссылок на следующий элемент в списке. | Как можно модифицировать алгоритм? Например, сделать изкаждой ячейки массива А список, в который будем добавлять структуры с одинаковыми ключами. Однако, этот вариант плох тем, что надо поддерживать сам список, что не является самым простым решением. К тому же нам надо будет хранить дополнительную информацию в виде ссылок на следующий элемент в списке. | ||
| Строка 14: | Строка 16: | ||
* Пусть для определенности P[1], P[2], ..., P[k] не равны нулю. Тогда разобьем массив А на k блоков, длина каждого из которых равна соотв. P[1], P[2], ..., P[k], и поставим над первым элементом каждого блока по указателю point_i, который в дальнейшем будет указывать на первый свободный элемент в своем блоке i. | * Пусть для определенности P[1], P[2], ..., P[k] не равны нулю. Тогда разобьем массив А на k блоков, длина каждого из которых равна соотв. P[1], P[2], ..., P[k], и поставим над первым элементом каждого блока по указателю point_i, который в дальнейшем будет указывать на первый свободный элемент в своем блоке i. | ||
* Теперь массив Р нам больше не нужен. Тогда превратим его в массив, хранящий в Р[i] - сумму элементов от 0 до i - 1 старого массива Р. Это делается за один пробег по массиву. | * Теперь массив Р нам больше не нужен. Тогда превратим его в массив, хранящий в Р[i] - сумму элементов от 0 до i - 1 старого массива Р. Это делается за один пробег по массиву. | ||
| − | * Теперь собственно сортировка. | + | * Теперь собственно сортировка. Как мы определим на очередном шаге по массиву С, куда вставить текущий элемент? Очень просто. Посмотрим на поле key и запишем эту структурку в <tex>A[P[key] + point_{key}]</tex>. Таким образом, после завершения алгоритма в А будет содержаться наша последовательность в отсортированном виде (так как блоки расположены по возрастанию соотв. ключей). |
| − | Как мы определим на очередном шаге по массиву С, куда вставить текущий элемент? Очень просто. Посмотрим на поле key и запишем эту структурку в A[P[key] + | ||
Стоит также отметить, что эта сортировка устойчивая, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в котором просматривались в изначальном массиве. | Стоит также отметить, что эта сортировка устойчивая, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в котором просматривались в изначальном массиве. | ||
Версия 23:59, 16 мая 2011
Постановка задачи
Иногда надо отсортировать набор каких либо "сложных" данных, например, структур, в которых несколько полей, и сортировать надо по одному из них. В данном случае для сортировки подсчетом предполагается, что величины, хранящиеся в данных ключах, являются целыми числами от 0 до k - 1.
Мы будем использовать все тот же алгоритм, что и для обыкновенных целых чисел, но с небольшой модификацией. Она необходима для разрешения следующей проблемы: разные структуры могут иметь одинаковые ключи. Нам надо каким-либо образом это учитывать.
Решение
Пусть далее исходня последовательность из n структур хранится в массиве С, а отсортированная - в А, причем ее ключи прина Как можно модифицировать алгоритм? Например, сделать изкаждой ячейки массива А список, в который будем добавлять структуры с одинаковыми ключами. Однако, этот вариант плох тем, что надо поддерживать сам список, что не является самым простым решением. К тому же нам надо будет хранить дополнительную информацию в виде ссылок на следующий элемент в списке.
Избавиться от этих недостатков можно следующим образом.
- Подсчитаем количество разных ключей в списке (пусть их будет k), а также количество ключей каждого вида. Пусть массив Р[i] содержит количество ключей, равных i. Очевидно, что это делается за О(n).
- Пусть для определенности P[1], P[2], ..., P[k] не равны нулю. Тогда разобьем массив А на k блоков, длина каждого из которых равна соотв. P[1], P[2], ..., P[k], и поставим над первым элементом каждого блока по указателю point_i, который в дальнейшем будет указывать на первый свободный элемент в своем блоке i.
- Теперь массив Р нам больше не нужен. Тогда превратим его в массив, хранящий в Р[i] - сумму элементов от 0 до i - 1 старого массива Р. Это делается за один пробег по массиву.
- Теперь собственно сортировка. Как мы определим на очередном шаге по массиву С, куда вставить текущий элемент? Очень просто. Посмотрим на поле key и запишем эту структурку в . Таким образом, после завершения алгоритма в А будет содержаться наша последовательность в отсортированном виде (так как блоки расположены по возрастанию соотв. ключей).
Стоит также отметить, что эта сортировка устойчивая, так как два элемента с одинаковыми ключами будут добавлены в том же порядке, в котором просматривались в изначальном массиве.
