АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Быстрая сортировка
  2. МЕДИЦИНСКАЯ СОРТИРОВКА.
  3. Медсортировка и эвакуация.
  4. Сортировка бинарными вставками
  5. Сортировка и фильтрация данных.
  6. Сортировка массивов. Поиск элемента массива.
  7. Сортировка почты (это рациональнее, чем сразу отвечать на все письма)

 

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

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

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

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

 

Алгоритм:

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

k1≤…≤kn

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

а12,…,аm.

 

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

r←N,b←1.

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

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

Rl≤…≤Rrпо биту b.

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

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

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

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

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

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

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

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

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

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

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

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

Rl…Rr отсортирован. Если в файле не может быть равных ключей, то такую проверку можно не делать. Иначе, если 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. Сортировка. Методы выбора и слияния. Простой, квадратичный выбор. Выбор из дерева. Двухпутевое слияние. Метод слияния списков.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)