Метод сортировки

Основные идеи и характеристики применяемых методов

Метод Цифровой сортировки

Методом сортировки последовательностей является цифровая сортировка. Пусть дана последовательность из S чисел, представленных в m–ичной системе счисления. Каждое число состоит из L цифр d1d2…dL, 0 ≤ di ≤ m – 1, i=1..L. Сначала числа из списка S распределяются по m очередям, причём номер очереди определяется последней цифрой каждого числа. Затем полученные очереди соединяются в список, для которого все действия повторяются, но распределение по очередям производится в соответствии со следующей цифрой и т.д.

Цифровой метод может успешно использоваться не только для сортировки чисел, но и для сортировки любой информации, представленной в памяти компьютера. Необходимо лишь рассматривать каждый байт ключа сортировки как цифру, принимающую значения от 0 до 255. Тогда для сортировки потребуется m=256 очередей. Для выделения каждого байта ключа сортировки можно использовать массив Digit, наложенный в памяти компьютера на поле элемента последовательности, по которому происходит сортировка.

Для цифровой сортировки М<const L(m+n). При фиксированных m и L М=O(n) при n → ∞, что значительно быстрее остальных рассмотренных методов. Однако если длина чисел L велика, то метод может проигрывать обычным методам сортировки. Кроме того, Метод применим только, если задача сортировки сводится к задаче упорядочивания чисел, что не всегда возможно.

Метод обеспечивает устойчивую сортировку. Чтобы изменить направление сортировки на обратное, очереди нужно присоединять в обратном порядке.

Дата добавления: 2015-07-26; просмотров: 183; Нарушение авторских прав

Мы поможем в написании ваших работ!