Обменная поразрядная сортировка

Вместо того чтобы сравнивать между собой два ключа, в этом методе проверяется, равны ли нулю или единице отдельные биты ключа от старшего бита к младшему. Рассмотрим метод, напоминающий метод быстрой сортировки, но использующий двоичное представление ключей. Здесь, вместо арифметических сравнений ключей проверяется, равны ли нулю или единице отдельные биты ключей.

В общих чертах идея метода следующая:

I этап. Файл сортируется по старшему значащему биту ключа так, что все ключи, начинающиеся с нуля, оказываются перед всеми ключами, начинающимися с единицы. Для этого надо найти самый левый ключ k_i, начинающийся с единицы и самый правый k_j, начинающийся с нуля, после чего, записи R_i и R_jменяются местами. Процесс повторяется до тех пор, пока не станет i>j.

II этап. Обозначим через F₀ множество элементов, начинающихся с нуля, а через F₁ – остальные. Применим к F0 обменную поразрядную сортировку (начинаем теперь со второго бита слева) до тех пор, пока множество F₀ не будет полностью отсортировано. Затем проделываем то же самое с множеством F₁. Как и при быстрой сортировке, для хранения информации о подфайлах, ожидающих сортировку, можно воспользоваться стеком. Стратегию формирования стека здесь применяют другую: В стек помещать не больший из подфайлов, а правый подфайл, при этом элементы стека (r,l) означают, что подфайл с правой границей r ожидает сортировку по биту l, левую границу можно не запоминать, она всегда задана неявно, так как файл обрабатывается слева на право.

Алгоритм:

Записи от 1-й до N-й R₁,R₂,…,R_Nпереразмещаются на том же месте. После завершения сортировки их ключи будут упорядочены

k₁≤…≤k_n

Предполагается, что все ключи – это m-разрядные двоичные числа:

а₁,а₂,…,а_m.

R1 [Начальная установка.] Опустошить стек, установить l←1,

r←N,b←1.

R2 [Начать новую стадию.] Сортируется подфайл записей со

следующими границами:

R_l≤…≤R_rпо биту b.

По смыслу алгоритма l≤r; если r=l, то перейти к R₁₀, в

противном случае i←l,j←r.

R3 [Проверить k i на единицу.] Проверить бит b ключа k i на единицу.

Если (k_i)_b=1, то перейти к шагу R6.

R4 [Увеличить i.] Если i≤j, то возвратиться к R3, иначе к шагу R8.

R5 [Проверить k j+1 на ноль.] Проверяется бит b ключа k_j+1.

Если (k_j+1)_b=0, то перейти к шагу R7.

R6 [Уменьшить j.] Уменьшить j на 1. j←j-1.Если i≤j, то перейти к шагу R₅, иначе к R₈.

R7 [Поменять местами записи R_iи R_j+1. ] Поменять местами R_i и R_j+1, затем перейти к шагу R4.

R8 [Проверить особые случаи.] К этому моменту стадия разделения

завершена, i=j+1, бит b ключей от k_l до k_j равен нулю, а бит ключей от k_i до k_r равен единице. Увеличить b на 1. Если b<m,где m – число бит,

или меньше, то перейти к шагу R10. Это значит, что подфайл

R_l…R_r отсортирован. Если в файле не может быть равных ключей, то такую проверку можно не делать. Иначе, если j<1 или j=r, возвратиться к шагу R2 (все просмотренные биты оказались равными соответственно

единице или нулю).

Если j=l, то увеличить l на 1 и перейти к шагу R2 (встретился

только один бит, равный нулю).

R9 [Поместить в стек.] Поместить в стек пару (r,b), затем установить

r←j и перейти к R2.

R10 [Взять из стека.] Если стек пуст, то сортировка закончена, иначе

установить l←r+1, взять из стека элемент (r’,b’), установить

r←r’,b←b’ и возвратиться к шагу R2.

Для хранения “информации о границах” подфайлов, ожидающих сортировки мы воспользуемся стеком.

Вместо того, чтобы сортировать в первую очередь наименьший из подфайлов, удобно продвигаться слева направо, т.к. размер стека в этом случае никогда не превзойдёт числа битов в сортируемых ключах.

8. Сортировка. Методы выбора и слияния. Простой, квадратичный выбор. Выбор из дерева. Двухпутевое слияние. Метод слияния списков.

Поиск по сайту: