Предположим, мой ввод (a,b и c для различения одинаковых ключей)
1 6a 8 3 6b 0 6c 4
Моя сортировка подсчета будет сохранена как (отбрасывая информацию a, b и c!!)
0(1) 1(1) 3(1) 4(1) 6(3) 8(1)
что даст мне результат
0 1 3 4 6 6 6 8
Итак, каков этот стабильный вид? Я не уверен, как это «поддерживает относительный порядок записей с одинаковыми ключами».
Пожалуйста, объясни.
На самом деле просто: вместо простого счетчика для каждого «сегмента» это связанный список.
То есть вместо
0(1) 1(1) 3(1) 4(1) 6(3) 8(1)
Ты получаешь
0(.) 1(.) 3(.) 4(.) 6(a,b,c) 8(.)
(здесь я использую . для обозначения некоторого элемента в ведре).
Затем просто сбросьте их обратно в один отсортированный список:
0 1 3 4 6a 6b 6c 8
То есть, когда вы находите элемент с ключом x, зная, что он может иметь другую информацию, которая отличает его от других элементов с тем же ключом, вы не просто увеличиваете счетчик для корзины x (что отбрасывает всю эту дополнительную информацию). .
Вместо этого у вас есть связанный список (или аналогично упорядоченная структура данных с амортизированным добавлением с постоянным временем) для каждой корзины, и вы добавляете этот элемент в конец списка для корзины x при просмотре ввода слева направо.
Таким образом, вместо того, чтобы использовать O(k) пространства для k счетчиков, у вас есть O(k) изначально пустых списков, сумма длин которых будет равна n в конце "счетной" части алгоритма. Этот вариант сортировки подсчетом по-прежнему будет O(n + k), как и раньше.
Чтобы понять, почему сортировка подсчетом стабильна, нужно понимать, что сортировку подсчетом можно использовать не только для сортировки списка целых чисел, но и для сортировки списка элементов, ключ которых является целым числом, и эти элементы будут отсортированы. по своим ключам, имея при этом дополнительную информацию, связанную с каждым из них.
Пример сортировки подсчетом, которая сортирует элементы с дополнительной информацией, поможет вам понять это. Например, мы хотим отсортировать три акции по их ценам:
[(GOOG 3), (CSCO 1), (MSFT 1)]
Здесь цены акций являются целочисленными ключами, а названия акций — связанной с ними информацией.
Ожидаемый результат сортировки должен быть следующим:
[(CSCO 1), (MSFT 1), (GOOG 3)]
(containing both stock price and its name,
and the CSCO stock should appear before MSFT so that it is a stable sort)
Массив counts будет рассчитан для сортировки этого (скажем, цены акций могут быть только от 0 до 3):
counts array: [0, 2, 0, 1] (price "1" appear twice, and price "3" appear once)
Если вы просто сортируете целочисленный массив, вы можете просмотреть массив counts и вывести «1» дважды и один раз «3», и это будет сделано, и после этого весь массив counts станет нулевым массивом.
Но здесь мы хотим, чтобы названия акций также отображались при сортировке. Как мы можем получить эту дополнительную информацию (похоже, массив counts уже отбрасывает эту часть информации)? Итак, связанная информация хранится в исходном несортированном массиве. В несортированном массиве [(GOOG 3), (CSCO 1), (MSFT 1)] у нас есть как название акции, так и ее цена. Если мы узнаем, какая позиция (GOOG 3) должна быть в конечном отсортированном массиве, мы можем скопировать этот элемент в отсортированную позицию в отсортированном массиве.
Чтобы получить конечную позицию для каждого элемента в отсортированном массиве, в отличие от сортировки целочисленного массива, вы не используете массив counts напрямую для вывода отсортированных элементов. Вместо этого сортировка с подсчетом имеет дополнительный шаг, который вычисляет массив совокупной суммы из массива counts:
counts array: [0, 2, 2, 3] (i from 0 to 3: counts[i] = counts[i] + counts[i - 1])
Этот кумулятивный массив сумм сообщает нам текущее положение каждого значения в окончательном отсортированном массиве. Например, counts[1]==2 означает, что текущий элемент со значением 1 должен быть помещен в слот 2nd в отсортированном массиве. Интуитивно, поскольку counts[i] является кумулятивной суммой слева, она показывает, сколько меньших элементов находится перед значением ith, что говорит вам, где должно быть положение для значения ith.
Если акция с ценой $1 появляется в первый раз, она должна быть выведена на вторую позицию отсортированного массива, а если акция с ценой $3 появляется в первый раз, она должна быть выведена на третью позицию отсортированного массива. Если появится акция за 1 доллар и ее элемент будет скопирован в отсортированный массив, мы уменьшим ее количество в массиве counts.
counts array: [0, 1, 2, 3]
(so that the second appearance of $1 price stock's position will be 1)
Таким образом, мы можем перебрать несортированный массив в обратном порядке (это важно для обеспечения стабильности), проверить его положение в отсортированном массиве в соответствии с массивом counts и скопировать его в отсортированный массив.
sorted array: [null, null, null]
counts array: [0, 2, 2, 3]
iterate stocks in unsorted stocks from backwards
1. the last stock (MSFT 1)
sorted array: [null, (MSFT 1), null] (copy to the second position because counts[1] == 2)
counts array: [0, 1, 2, 3] (decrease counts[1] by 1)
2. the middle stock (CSCO 1)
sorted array: [(CSCO 1), (MSFT 1), null] (copy to the first position because counts[1] == 1 now)
counts array: [0, 0, 2, 3] (decrease counts[1] by 1)
3. the first stock (GOOG 3)
sorted array: [(CSCO 1), (MSFT 1), (GOOG 3)] (copy to the third position because counts[3] == 3)
counts array: [0, 0, 2, 2] (decrease counts[3] by 1)
Как видите, после сортировки массива массив counts (то есть [0, 0, 2, 2]) не становится массивом со всеми нулями, как при сортировке массива целых чисел. Массив counts не используется для определения того, сколько раз целое число появляется в несортированном массиве, вместо этого он используется для определения позиции элемента в конечном отсортированном массиве. И поскольку мы уменьшаем количество каждый раз, когда выводим элемент, мы, по сути, уменьшаем элементы с конечной позицией следующего появления одной и той же клавиши. Вот почему нам нужно перебирать несортированный массив в обратном порядке, чтобы обеспечить его стабильность.
Вывод:
Поскольку каждый элемент содержит не только целое число в качестве ключа, но и некоторую дополнительную информацию, даже если их ключ одинаков, вы можете сказать, что каждый элемент отличается, используя дополнительную информацию, поэтому вы сможете определить, является ли он стабильным. алгоритм сортировки (да, это стабильный алгоритм сортировки, если он реализован соответствующим образом).
Ссылки:
Некоторые хорошие материалы, объясняющие сортировку подсчета и ее стабильность:
Ваше решение не является сортировкой с полным подсчетом и отбрасывает связанные значения.
Вот полный алгоритм сортировки подсчетом.
После того, как вы рассчитали гистограмму:
0(1) 1(1) 3(1) 4(1) 6(3) 8(1)
вам нужно рассчитать накопленные суммы - каждая ячейка будет содержать, сколько элементов меньше или равно этому значению:
0(1) 1(2) 3(3) 4(4) 6(7) 8(8)
Теперь вы начинаете с конца исходного списка и идете назад.
Последний элемент 4. Есть 4 элемента, меньших или равных 4. Таким образом, 4 займет 4-ю позицию. Вы уменьшаете счетчик для 4.
0(1) 1(2) 3(3) 4(3) 6(7) 8(8)
Следующий элемент 6c. Есть 7 элементов, меньших или равных 6. Таким образом, 6c переместится на 7-ю позицию. Опять же, вы уменьшаете значение счетчика для 6.
0(1) 1(2) 3(3) 4(3) 6(6) 8(8)
^ next 6 will go now to 6th position
Как видите, этот алгоритм является стабильной сортировкой. Порядок элементов с одинаковым ключом будет сохранен.
Если ваши три значения «6» различимы, то ваша сортировка по подсчету неверна (она отбрасывает информацию о значениях, чего не делает истинная сортировка, потому что истинная сортировка только переупорядочивает значения).
Если ваши три значения «6» неразличимы, то сортировка стабильна, потому что у вас есть три неразличимых «6» на входе и три на выходе. Бессмысленно говорить о том, были ли они «перезаказаны» или нет: они идентичны.
Концепция нестабильности применяется только тогда, когда значения имеют некоторую связанную информацию, которая не участвует в порядке. Например, если вы сортировали указатели на эти целые числа, то вы могли бы «указать разницу» между тремя шестерками, взглянув на их разные адреса. Тогда имело бы смысл спросить, стабилен ли какой-либо конкретный сорт. Тогда сортировка подсчетом, основанная на целочисленных значениях, не будет сортировать указатели. Сортировка подсчетом, основанная на значениях указателя, упорядочивает их не по целочисленному значению, а по адресу.
