Полная версия

Главная arrow Информатика arrow Алгоритмы и структуры данных

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ВНУТРЕННЯЯ СОРТИРОВКА

Сортировка выполняется или над самими записями, или над указателями вспомогательной таблицы адресов.

Сортировка самих записей показана на рис. 5.1.

Первоначальная Отсортированная последовательность последовательность

ключ

Запись 1

4

Запись 2

2

ввв

Запись 3

1

ААА

Запись 4

5

ЕЕЕ

Запись 5

3

ССС

Рис. 5.1. Сортировка записей

ключ

1

ААА

2

ВВВ

3

ССС

4

ОЭО

5

ЕЕЕ

Сортировка таблицы указателей (адресов) используется, если объем данных, помещенных в каждую запись, такой, что перемещение записей связано с большими затратами (см. рис. 5.2).

Первоначальная Отсортированная

таблица указателей таблица указателей

ключ

  • 2
  • 4
  • 5
  • 1
  • 3
  • 5

Рис. 5.2. Сортировка таблицы адресов

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

СОРТИРОВКА ПОДСЧЕТОМ

Простой подсчет. Метод основан на очевидном утверждении: если в отсортированной последовательности элемент находится на /-м месте, то его ключ превышает / -1 ключей предшествующих элементов. Алгоритм сортировки предполагает подсчет числа ключей к/, меньших ключа /-го элемента исходной последовательности, по рекуррентной формуле

kj = kj +1, если а/ > Oj, i,j = 1,2,3,..., n.

Заметим, что запись я, > ctj является условной — фактически осуществляется сравнение ключей элементов я, и cij, что соответствует программному коду я[/].кеу > я[/].кеу.

Вычисленные значения kj сохраняются в массиве адресов длиной п. В отсортированной последовательности /-й элемент из исходной последовательности помещается на (к,• + 1)-е место.

Для расстановки элементов в соответствии с вычисленными адресами необходимо увеличить все элементы массива адресов на 1, чтобы получить адрес каждого элемента в результирующей последовательности, а затем менять местами элементы сортируемого массива с теми элементами, которые стоят на их местах, и параллельно переставлять местами соответствующие элементы массива адресов.

В приведенном ниже участке программы Item и Addr — вспомогательные переменные для хранения элемента и его адреса.

// расстановка элементов a[i] по адресам,

//хранящимся в массиве k[i] for i:=1 to n do lnc(k[i]);

for i:=1 to n-1 do begin while i<>k[i] do begin ltem:=a[ij; a[i]:=a[k[i]]; a[k[i]]:=ltem;

Addr:=k[i]; k[i]:=k[Addr]; k[Addr]:=Addr;

end;

end;

Метод простого подсчета применим только для последовательностей с неповторяющимися элементами. Он требует дополнительной памяти для хранения п адресов элементов.

В процессе сортировки необходимо выполнить п2 сравнений, 3/7 пересылок элементов и 3/7 пересылок адресов при расстановке элементов массива по найденным адресам.

Модифицированный метод подсчета. Если исходная последовательность содержит элементы с одинаковыми ключами, то метод подсчета нужно модифицировать следующим образом. При определении адреса /-го элемента исходной последовательности в результирующей последовательности элемент ai сравнивается со следующими за ним /7-/ элементами, и значения счетчиков адресов определяются по рекуррентным формулам: kj =kj +1, если <2, > Oj , kj =kj +1, если at < af,

/ = 1,2, ..., /7-1; j = i+1,/ + 2,...,/7,

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

Метод требует /7 элементов дополнительной памяти для хранения адресов элементов. Для сортировки необходимо выполнить С- 0,5/7(/7-1) ~ 0,5/72 сравнений, 3/7 пересылок элементов И 3/7 пересылок адресов.

 
<<   СОДЕРЖАНИЕ   >>