ЛЕКЦИЯ №1
Эта лекция посвящена сугубо алгоритмической проблеме упорядочения данных. Приемы работы с символьными и строковыми данными. Использование множеств. Задание больших множеств массивами.
Задача сортировки
Необходимость отсортировать какие-либо величины возникает в программировании очень часто. К примеру, входные данные подаются "вперемешку", а вашей программе удобнее обрабатывать упорядоченную последовательность. Существуют ситуации, когда предварительная сортировка данных позволяет сократить содержательную часть алгоритма в разы, а время его работы - в десятки раз.
Однако верно и обратное. Сколь бы хорошим и эффективным ни был выбранный вами алгоритм, но если в качестве подзадачи он использует "плохую" сортировку, то вся работа по его оптимизации оказывается бесполезной. Неудачно реализованная сортировка входных данных способна заметно понизить эффективность алгоритма в целом.
Методы упорядочения подразделяются на внутренние (обрабатывающие массивы) и внешние (занимающиеся только файлами)1).
Эту лекцию мы посвятим только внутренним сортировкам. Их важная особенность состоит в том, что эти алгоритмы не требуют дополнительной памяти: вся работа по упорядочению производится внутри одного и того же массива.
Простые сортировки
К простым внутренним сортировкам относят методы, сложность которых пропорциональна квадрату размерности входных данных. Иными словами, при сортировке массива, состоящего из N компонент, такие алгоритмы будут выполнять С*N2 действий, где С - некоторая константа.
Количество действий, необходимых для упорядочения некоторой последовательности данных, конечно же, зависит не только от длины этой последовательности, но и от ее структуры. Например, если на вход подается уже упорядоченная последовательность (о чем программа, понятно, не знает), то количество действий будет значительно меньше, чем в случае перемешанных входных данных.
Как правило, сложность алгоритмов подсчитывают раздельно по количеству сравнений и по количеству перемещений данных в памяти (пересылок), поскольку выполнение этих операций занимает различное время. Однако точные значения удается найти редко, поэтому для оценки алгоритмов ограничиваются лишь понятием "пропорционально", которое не учитывает конкретные значения констант, входящих в итоговую формулу. Общую же эффективность алгоритма обычно оценивают "в среднем": как среднее арифметическое от сложности алгоритма "в лучшем случае" и "в худшем случае", то есть (Eff_best + Eff_worst)/2.
Сортировка простыми вставками
Самый простой способ сортировки2), который приходит в голову, - это упорядочение данных по мере их поступления. В этом случае при вводе каждого нового значения можно опираться на тот факт, что все предыдущие элементы уже образуют отсортированную последовательность.
Алгоритм ПрВст
- Первый элемент записать "не раздумывая".
- Пока не закончится последовательность вводимых данных, для каждого нового ее элемента выполнять следующие действия:
- начав с конца уже существующей упорядоченной последовательности, все ее элементы, которые больше, чем вновь вводимый элемент, сдвинуть на 1 шаг назад;
- записать новый элемент на освободившееся место.
При этом, разумеется, можно прочитать все вводимые элементы одновременно, записать их в массив, а потом "воображать", что каждый очередной элемент был введен только что. На суть и структуру алгоритма это не повлияет.
Реализация алгоритма ПрВст
for i:= 2 to N do
if a[i-1]>a[i] then {*}
begin x:= a[i];
j:= i-1;
while (j>0)and(a[j]>x) do {**}
begin a[j+1]:= a[j];
j:= j-1;
end;
a[j+1]:= x;
end;
Метод прямых вставок с барьером (ПрВстБар)
Для того чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний var) и будем записывать в нее поочередно каждый вставляемый элемент (сравните строки {*} и {**} в приведенных вариантах программы). В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как "барьер", не дающий индексу j выйти за нижнюю границу массива. Кроме того, компонента a[0] может заменить собою и дополнительную переменную х:
for i:= 2 to N do
if a[i-1]>a[i] then
begin a[0]:= a[i]; {*}
j:= i-1;
while a[j]>a[0] do {**}
begin a[j+1]:= a[j];
j:= j-1;
end;
a[j+1]:= a[0];
end;
Эффективность алгоритма ПрВстБар
Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм ПрВстБар совершит N-1 сравнение и 0 пересылок данных.
В худшем же случае - когда входная последовательность упорядочена "наоборот" - сравнений будет уже (N+1)*N/2, а пересылок (N-1)*(N+3). Таким образом, этот алгоритм имеет сложность ~N2 (читается "порядка эн квадрат") по обоим параметрам.
Пример сортировки
Предположим, что нужно отсортировать следующий набор чисел:
5 3 4 3 6 2 1
Выполняя алгоритм ПрВстБар, мы получим такие результаты (подчеркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):
Состояние массива Сдвиги Сравнения Пересылки данных
0 шаг: 5343621
1 шаг: 5343621 1 1+1
1+22 шаг: 3543621 1 1+1 1+2 3 шаг: 3453621 2 2+1 2+2 4 шаг: 3345621 0 1 0 5 шаг: 3345621 5 5+1 5+2 6 шаг: 2334561 6 6+1 6+2 Результат: 1233456 15 20 25
Сортировка бинарными вставками
Сортировку простыми вставками можно немного улучшить: поиск "подходящего места" в упорядоченной последовательности можно вести более экономичным способом, который называется Двоичный поиск в упорядоченной последовательности. Он напоминает детскую игру "больше-меньше": после каждого сравнения обрабатываемая последовательность сокращается в два раза.
Пусть, к примеру, нужно найти место для элемента 7 в таком массиве:
[2 4 6 8 10 12 14 16 18]
Найдем средний элемент этой последовательности (10) и сравним с ним семерку. После этого все, что больше 10 (да и саму десятку тоже), можно смело исключить из дальнейшего рассмотрения:
[2 4 6 8] 10 12 14 16 18
Снова возьмем середину в отмеченном куске последовательности, чтобы сравнить ее с семеркой. Однако здесь нас поджидает небольшая проблема: точной середины у новой последовательности нет, поэтому нужно решить, который из двух центральных элементов станет этой "серединой". От того, к какому краю будет смещаться выбор в таких "симметричных" случаях, зависит окончательная реализация нашего алгоритма. Давайте договоримся, что новой "серединой" последовательности всегда будет становиться левый центральный элемент. Это соответствует вычислению номера "середины" по формуле
nomer_sred:= (nomer_lev + nomer_prav)div 2
Итак, отсечем половину последовательности:
2 4 [6 8] 10 12 14 16 18
И снова:
2 4 6 [8] 10 12 14 16 18 2 4 6][8 10 12 14 16 18
Таким образом, мы нашли в исходной последовательности место, "подходящее" для нового элемента. Если бы в той же самой последовательности нужно было найти позицию не для семерки, а для девятки, то последовательность границ рассматриваемых промежутков была бы такой:
[2 4 6 8] 10 12 14 16 18 2 4 [6 8] 10 12 14 16 18 2 4 6 [8] 10 12 14 16 18 2 4 6 8][10 12 14 16 18
Из приведенных примеров уже видно, что поиск ведется до тех пор, пока левая граница не окажется правее(!) правой границы. Кроме того, по завершении этого поиска последней левой границей окажется как раз тот элемент, на котором необходимо закончить сдвиг "хвоста" последовательности.
Будет ли такой алгоритм универсальным? Давайте проверим, что же произойдет, если мы станем искать позицию не для семерки или девятки, а для единицы:
[2 4 6 8] 10 12 14 16 18 [2] 4 6 8 10 12 14 16 18 ][2 4 6 8 10 12 14 16 18
Как видим, правая граница становится неопределенной - выходит за пределы массива. Будет ли этот факт иметь какие-либо неприятные последствия? Очевидно, нет, поскольку нас интересует не правая, а левая граница.
"А что будет, если мы захотим добавить 21?" - спросит особо въедливый читатель. Проверим это:
2 4 6 8 10 [12 14 16 18] 2 4 6 8 10 12 14 [16 18] 2 4 6 8 10 12 14 16 [18] 2 4 6 8 10 12 14 16 18][
Кажется, будто все плохо: левая граница вышла за пределы массива; непонятно, что нужно сдвигать...
Вспомним, однако, что в реальности на (N+1)-й позиции как раз и находится вставляемый элемент (21). Таким образом, если левая граница вышла за рассматриваемый диапазон, получается, что ничего сдвигать не нужно. Вообще же такие действия выглядят явно лишними, поэтому от них стоит застраховаться, введя одну дополнительную проверку в текст алгоритма.
Реализация алгоритма БинВст
for i:= 2 to n do
if a[i-1]>a[i] then
begin x:= a[i];
left:= 1;
right:= i-1;
repeat
sred:= (left+right)div 2;
if a[sred]<x then left:= sred+1
else right:= sred-1;
until left>right;
for j:= i-1 downto left do a[j+1]:= a[j];
a[left]:= x;
end;
Эффективность алгоритма БинВст
Теперь на каждом шаге выполняется не N, а log N проверок5), что уже значительно лучше (для примера, сравните 1000 и 10 = log 1024). Следовательно, всего будет совершено N*log N сравнений. Впрочем, улучшение это не слишком значительное, ведь по количеству пересылок наш алгоритм по-прежнему имеет сложность "порядка N2".
Сортировка простым выбором
Попробуем теперь сократить количество пересылок элементов.
Алгоритм ПрВыб
На каждом шаге (всего их будет ровно N-1) будем производить такие действия:
- найдем минимум среди всех еще не упорядоченных элементов;
- поменяем его местами с первым "по очереди" не отсортированным элементом. Мы надеемся, что читателям очевидно, почему к концу работы этого алгоритма последний (N-й) элемент массива автоматически окажется максимальным.
Реализация ПрВыб
for i:= 1 to n-1 do
begin min_ind:= i;
for j:= i+1 to n do
if a[j]<=a[min_ind] {***}
then min_ind:= j;
if min_ind<>i
then begin
x:= a[i];
a[i]:= a[min_ind];
a[min_ind]:= x;
end;
end;
Эффективность алгоритма ПрВыб
В лучшем случае (если исходная последовательность уже упорядочена), алгоритм ПрВыб произведет (N-1)*(N+2)/2 сравнений и 0 пересылок данных. В остальных же случаях количество сравнений останется прежним, а вот количество пересылок элементов массива будет равным 3*(N-1).
Таким образом, алгоритм ПрВыб имеет квадратичную сложность (~N2) по сравнениям и линейную (~N) - по пересылкам.
Замечание. Если перед вами поставлена задача отсортировать строки двумерного массива (размерности NxN) по значениям его первого столбца, то сложность алгоритма ПрВыб, модифицированного для решения этой задачи, будет квадратичной (N2 сравнений и N2 пересылок), а алгоритма БинВст - кубической (N*log N сравнений и N3 пересылок). Комментарии, как говорится, излишни.
Пример сортировки
Предположим, что нужно отсортировать тот же набор чисел, при помощи которого мы иллюстрировали метод сортировки простыми вставками:
5 3 4 3 6 2 1
Теперь мы будем придерживаться алгоритма ПрВыб (подчеркнута несортированная часть массива, а квадратиком выделен ее минимальный элемент):
1 шаг: 5343621
2 шаг: 1343625
3 шаг: 1243635 {***}
4 шаг: 1233645{ничего не делаем} 5 шаг: 1233645 6 шаг: 1233465 результат: 1233456
Сортировка простыми обменами
Рассмотренными сортировками, конечно же, не исчерпываются все возможные методы упорядочения массивов.
Существуют, например, алгоритмы, основанные на обмене двух соседних элементов: Пузырьковая и Шейкерная сортировки. Обе имеют сложность порядка N2, однако и по скорости работы на любых входных данных, и по простоте реализации они проигрывают другим простым сортировкам. Поэтому мы настойчиво советуем читателю не прельщаться красивыми названиями, за которыми не стоит никакой особенной выгоды.
Тем же, кто все-таки желает ознакомиться с обменными сортировками, а также с подробными данными по сравнению различных сортировок, мы рекомендуем труды Д. Кнута7) или Н. Вирта8).
Улучшенные сортировки
В отличие от простых сортировок, имеющих сложность ~N2, к улучшенным сортировкам относятся алгоритмы с общей сложностью ~N*logN.
Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N<100) эффективность быстрых сортировок не столь очевидна: выигрыш становится заметным только при больших N. Следовательно, если необходимо отсортировать маленький набор данных, то выгоднее взять одну из простых сортировок.
Сортировка Шелла
Эта сортировка9) базируется на уже известном нам алгоритме простых вставок ПрВст. Смысл ее состоит в раздельной сортировке методом ПрВст нескольких частей, на которые разбивается исходный массив. Эти разбиения помогают сократить количество пересылок: для того, чтобы освободить "правильное" место для очередного элемента, приходится уже сдвигать меньшее количество элементов.
Алгоритм УлШелл
На каждом шаге (пусть переменная t хранит номер этого шага) нужно произвести следующие действия:
- вычленить все подпоследовательности, расстояние между элементами которых составляет kt;
- каждую из этих подпоследовательностей отсортировать методом ПрВст.
Нахождение убывающей последовательности расстояний kt, kt-1..., k1 составляет главную проблему этого алгоритма. Многочисленные исследования позволили выявить ее обязательные свойства:
- k1 = 1;
- для всех t kt > kt-1;
- желательно также, чтобы все kt не были кратными друг другу (для того, чтобы не повторялась обработка ранее отсортированных элементов).
Дональд Кнут предлагает две "хорошие" последовательности расстояний:
1, 4, 13, 40, 121, _ (k
t= 1+3*kt-1) 1, 3, 7, 15, 31, _ (kt= 1+2*kt-1= 2t-1)
Первая из них подходит для сортировок достаточно длинных массивов, вторая же более удобна для коротких. Поэтому мы остановимся именно на ней (желающим запрограммировать первый вариант предоставляется возможность самостоятельно внести необходимые изменения в текст реализации алгоритма).
Как же определить начальное значение для t (а вместе с ним, естественно, и для kt)?
Можно, конечно, шаг за шагом проверять, возможно ли вычленить из сортируемого массива подпоследовательность (хотя бы длины 2) с расстояниями 1, 3, 7, 15 и т.д. между ее элементами. Однако такой способ довольно неэффективен. Мы поступим иначе, ведь у нас есть формула для вычисления kt = 2t -1.
Итак, длина нашего массива (N) должна попадать в такие границы:
k
t<= N -1 < kt+1
или, что то же самое,
2
t<= N < 2t+1
Прологарифмируем эти неравенства (по основанию 2):
t <= log N < t+1
Таким образом, стало ясно, что t можно вычислить по следующей формуле:
t = trunc(log N))
К сожалению, язык Pascal предоставляет возможность логарифмировать только по основанию е (натуральный логарифм). Поэтому нам придется вспомнить знакомое из курса средней школы правило "превращения" логарифмов:
log
mx =logzx/logzm
В нашем случае m = 2, z = e. Таким образом, для начального t получаем:
t:= trunc(ln(N)/ln(2)).
Однако при таком t часть подпоследовательностей будет иметь длину 2, а часть - и вовсе 1. Сортировать такие подпоследовательности незачем, поэтому стоит сразу же отступить еще на 1 шаг:
t:= trunc(ln(N)/ln(2))-1
Расстояние между элементами в любой подпоследовательности вычисляется так:
k:= (1 shl t)-1; {k= 2
t-1}
Количество подпоследовательностей будет равно в точности k. В самом деле, каждый из первых k элементов служит началом для очередной подпоследовательности. А дальше, начиная с (k+1)-го, все элементы уже являются членами некоторой, ранее появившейся подпоследовательности, значит, никакая новая подпоследовательность не сможет начаться в середине массива.
Сколько же элементов будет входить в каждую подпоследовательность? Ответ таков: если длину всей сортируемой последовательности (N) можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно:
s:= N div k;
Если же N не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на 1. Количество таких "удлиненных" подпоследовательностей совпадает с длиной "хвоста" - остатка от деления N на шаг k:
P:= N mod k;
Реализация алгоритма УлШелл
Ради большей наглядности мы пожертвовали эффективностью и воспользовались алгоритмом ПрВст, а не ПрВстБар или БинВст. Дотошному же читателю предоставляется возможность самостоятельно улучшить предлагаемую реализацию:
program shell_sort;
const n=18;
a:array[1..n] of integer
=(18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1);
var ii,m,x,s,p,t,k,r,i,j: integer;
begin
t:= trunc(ln(n)/ln(2));
repeat
t:= t-1;
k:= (1 shl t)-1;
p:= n mod k;
s:= n div k;
if p=0 then p:= k
else s:= s+1;
writeln(k,'-сортировка');
for i:= 1 to k do {берем и длинные, и короткие подпоследовательности}
begin
if i= p+1 then s:= s-1; (для коротких - уменьшаем длину}
for j:= 1 to s-1 do {метод ПрВст с шагом k}
if a[i+(j-1)*k]>a[i+j*k]
then begin x:= a[i+j*k];
m:= i+(j-1)*k;
while (m>0) and (a[m]>x) do
begin a[m+k]:= a[m];
m:= m-k;
end;
a[m+k]:= x;
end;
for ii:= 1 to n do write(a[ii],' ');
writeln;
end;
until k=1;
end.
Результат работы
7-сортировки
4 17 16 15 14 13 12 11 10 9 8 7 6 5 18 3 2 1
4 3 16 15 14 13 12 11 10 9 8 7 6 5 18 17 2 1
4 3 2 15 14 13 12 11 10 9 8 7 6 5 18 17 16 1
4 3 2 1 14 13 12 11 10 9 8 7 6 5 18 17 16 15
4 3 2 1 7 13 12 11 10 9 8 14 6 5 18 17 16 15
4 3 2 1 7 6 12 11 10 9 8 14 13 5 18 17 16 15
4 3 2 1 7 6 5 11 10 9 8 14 13 12 18 17 16 15
3-сортировки
1 3 2 4 7 6 5 11 10 9 8 14 13 12 18 17 16 15
1 3 2 4 7 6 5 8 10 9 11 14 13 12 18 17 16 15
1 3 2 4 7 6 5 8 10 9 11 14 13 12 15 17 16 18
1-сортировка
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Эффективность алгоритма УлШелл
Довольно сложными методами, в изложение которых мы не будем углубляться, показано, что алгоритм Шелла имеет сложность ~N3/2. И хотя это несколько хуже, чем N*logN, все-таки эта сортировка относится к улучшенным.
Пример сравнения сортировок: Вновь возьмем последовательность, для сортировки которой методом простых вставок ПрВст потребовалось 15 сдвигов (25 пересылок и 20 сравнений):
5 3 4 3 6 2 1
Теперь применим к ней метод Шелла.
Здесь N = 7, поэтому:
t= trunc(log 7) = 2
k= 2
2-1 = 3 {начнем с 3-сортировки} p= 7 mod 3 = 1 {кол-во длинных подпоследовательностей} s= (7 div 3)+1 = 3 {длина длинной подпоследовательности}
- 3-сортировки:
5 3 1 -> 1 3 5 {3 сдвига: 7 пересылок, 5 сравнений} 3 6 -> 3 6 {0 сдвигов: 0 пересылок, 1 сравнение} 4 2 -> 2 4 {1 сдвиг: 3 пересылки, 2 сравнения}Всего 4 сдвига: 10 пересылок, 8 сравнений Итог 3-сортировок: 1 3 2 3 6 4 5-
1-сортировка:
Состояние массива Сдвиги Сравнения Пересылки данных 0 шаг: 1323645 1 шаг: 1323645 0 1 0 2 шаг: 1323645 1 1+1 1+2 3 шаг: 1233645 0 1 0 4 шаг: 1233645 0 1 0 5 шаг: 1233645 1 1+1 1+2 6 шаг: 1233465 1 1+1 1+2 результат: 1233456 3 9 9
При сортировке методом Шелла в сумме получилось 7 сдвигов (19 пересылок и 17 сравнений). Выигрыш по сравнению с методом простых вставок составляет 53% (24% экономится на пересылках и 15% - на сравнениях)10). Если вместо метода простых вставок ПрВст использовать метод бинарных вставок БинВст, то выигрыш по количеству сравнений будет ощутимее.
Кроме того, не нужно забывать, что в нашем примере последовательность очень коротка: N = 7. Для больших N (скажем, N = 10000) преимущество метода Шелла станет еще заметнее.
Пирамидальная сортировка
Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором ПрВыб.
Р. Флойд предложил перестроить линейный массив в пирамиду - своеобразное бинарное дерево, - а затем искать минимум только среди тех элементов, которые находятся непосредственно "под" текущим вставляемым.
Просеивание
Для начала необходимо перестроить исходный массив так, чтобы он превратился в пирамиду, где каждый элемент "опирается" на два меньших. Этот процесс назвали просеиванием, потому что он очень напоминает процесс разделения некоторой смеси (камней, монет, т.п.) на фракции в соответствии с размерам частиц: на нескольких грохотах11) последовательно задерживаются сначала крупные, а затем все более мелкие частицы.
Итак, будем рассматривать наш линейный массив как пирамидальную структуру:
Видно, что любой элемент a[i] (1<=i<=N div 2) "опирается" на элементы a[2*i] и a[2*i+1]. И в каждой такой тройке максимальный элемент должен находится "сверху". Конечно, исходный массив может и не удовлетворять этому свойству, поэтому его потребуется немного перестроить.
Начнем процесс просеивания "снизу". Половина элементов (с ((N div 2)+1)-го по N-й) являются основанием пирамиды, их просеивать не нужно. А для всех остальных элементов (двигаясь от конца массива к началу) мы будем проверять тройки a[i], a[2*i] и a[2*i+1] и перемещать максимум "наверх" - в элемент a[i].
При этом, если в результате одного перемещения нарушается пирамидальность в другой (ниже лежащей) тройке элементов, там снова необходимо "навести порядок" - и так до самого "низа" пирамиды:
for i:= (N div 2)downto 1 do
begin j:= i;
while j<=(N div 2) do
begin k:= 2*j;
if (k+1<=N) and (a[k]<a[k+1])
then k:= k+1;
if a[k]>a[j]
then begin x:= a[j];
a[j]:= a[k];
a[k]:= x;
j:= k
end
else break
end
end;
Пример результата просеивания
Возьмем массив [1,7,5,4,9,8,12,11,2,10,3,6] (N = 12).
Его исходное состояние таково (серым цветом выделено "основание" пирамиды, не требующее просеивания):
После первых трех просеиваний (a[6], a[5], a[4]) получим такую картину (здесь и далее серым цветом выделяем участников просеивания):
Просеивание двух следующих элементов (a[3] и a[2]) тоже не вызовет вопросов - для каждого из них будет достаточно только одного шага:
А вот для просеивания последнего элемента (a[1]) понадобится целых три шага:
Итак, мы превратили исходный массив в пирамиду: в любой тройке a[i], a[2*i] и a[2*i+1] максимум находится "сверху".
Алгоритм УлПир
Для того чтобы отсортировать массив методом Пирамиды, необходимо выполнить такую последовательность действий:
0-й шаг: Превратить исходный массив в пирамиду (с помощью просеивания).
1-й шаг: Для N-1 элементов, начиная с последнего, производить следующие действия:
- поменять местами очередной "рабочий" элемент с первым;
- просеять (новый) первый элемент, не затрагивая, однако, уже отсортированный хвост последовательности (элементы с i-го по N-й).
Реализация алгоритма УлПир
Часть программы, реализующую нулевой шаг алгоритма УлПир, мы привели в пункте "Просеивание", поэтому здесь ограничимся только реализацией основного шага 1:
for i:= N downto 2 do
begin x:= a[1];
a[1]:= a[i];
a[i]:= x;
j:= 1;
while j<=((i-1)div 2) do
begin k:= 2*j;
if (k+1<=i-1) and (a[k]<a[k+1])
then k:= k+1;
if a[k]>a[j]
then begin x:= a[j];
a[j]:= a[k];
a[k]:= x;
j:= k
end
else break
end
end;
Пример. Продолжим сортировку массива, для которого мы уже построили пирамиду: [12,11,8,7,10,6,5,4,2,9,3,1]. С целью экономии места мы не будем далее прорисовывать структуру пирамиды, оставляя это несложное упражнение читателям. Подчеркивание будет отмечать элементы, участвовавшие в просеивании, а полужирный шрифт - элементы, исключенные из дальнейшей обработки:
1) Меняем местами a[1] и a[12]: [1,11,8,7,10,6,5,4,2,9,3,12]; 2) Просеиваем элемент a[1], получаем: [11,10,8,7,9,6,5,4,2,1,3,12]; 3) Меняем местами a[1] и a[11]: [3,10,8,7,9,6,5,4,2,1,11,12]; 4) Просеиваем a[1], получаем: [10,9,8,7,3,6,5,4,2,1,11,12]; 5) Меняем местами a[1] и a[10]: [1,9,8,7,3,6,5,4,2,10,11,12]; 6) Просеиваем элемент a[1]: [9,7,8,4,3,6,5,1,2,10,11,12]; 7) Меняем местами a[1] и a[9]: [2,7,8,4,3,6,5,1,9,10,11,12]; 8) Просеиваем элемент a[1]: [8,7,6,4,3,2,5,1,9,10,11,12]; 9) Меняем местами a[1] и a[8]: [1,7,6,4,3,2,5,8,9,10,11,12]; 10) Просеиваем элемент a[1]: [7,4,6,1,3,2,5,8,9,10,11,12]; 11) Меняем местами a[1] и a[7]: [5,4,6,1,3,2,7,8,9,10,11,12]; 12) Просеиваем элемент a[1]: [6,4,5,1,3,2,7,8,9,10,11,12]; 13) Меняем местами a[1] и a[6]: [2,4,5,1,3,6,7,8,9,10,11,12]; 14) Просеиваем элемент a[1]: [5,4,2,1,3,6,7,8,9,10,11,12]; 15) Меняем местами a[1] и a[5]: [3,4,2,1,5,6,7,8,9,10,11,12]; 16) Просеиваем элемент a[1]: [4,3,2,1,5,6,7,8,9,10,11,12]; 17) Меняем местами a[1] и a[4]: [1,3,2,4,5,6,7,8,9,10,11,12]; 18) Просеиваем элемент a[1]: [3,1,2,4,5,6,7,8,9,10,11,12]; 19) Меняем местами a[1] и a[3]: [2,1,3,4,5,6,7,8,9,10,11,12]; 20) Просеивать уже ничего не нужно; 21) Меняем местами a[1] и a[2]: [1,2,3,4,5,6,7,8,9,10,11,12]; 22) Просеивать ничего не нужно, сортировка закончена.
Эффективность алгоритма УлПир
Пирамидальная сортировка хорошо работает с большими массивами, однако на маленьких примерах (N<20) выгода от ее применения может быть не слишком очевидна.
В среднем этот алгоритм имеет сложность, пропорциональную N*log N.
Быстрая сортировка
Существует еще один метод улучшенной сортировки, имеющий среднюю сложность порядка N*log N: так называемая Быстрая сортировка12). Этот алгоритм является усовершенствованием обменных сортировок. Его реализация наиболее удобна в рекурсивном варианте, поэтому мы вернемся к ее изучению после того, как познакомимся с рекурсивными процедурами и функциями.
 |
|
|
2) В названиях алгоритмов мы будем следовать Кнуту.
3) Одно - при сдвиге и еще одно - при проверке необходимости сдвига
4) Одно - при сдвиге и еще две - при переписывании вставляемого элемента.
5) Напомним, что log N означает log2 N
6) Если бы в строке {***} программы ПРВыб стоял знак строгого неравенства, то в качестве минимума была бы выбрана первая тройка. Однако очевидно, что выгоднее брать последний из совпадающих элементов: благодаря этому все они оказываются левее, чем тот превосходящий всех их элемент, с которым выбранный минимум меняется местами.
7) Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск (любое издание).
8) Н. Вирт. Алгоритмы и структуры данных (любое издание).
9) Д. Л. Шелл назвал ее "сортировкой вставками с убывающим шагом".
10) Для других входных данных это число может быть значительно меньше или же еще больше.
11) Грохот - техническое "сито".
12) В оригинале QuickSort.
Символы и строки
Описание строк
В разделе var строки описываются следующим образом1):
var <имя_строки>: string[[<длина>]]2)
Максимальная длина строки - 255 символов. Нумеруются ее компоненты начиная с 0, но этот нулевой байт хранит длину строки.
Если <длина> не указана, то считается, что в строке 255 символов. Поэтому для экономии памяти следует по возможности точно указывать длину используемых строк.
Примеры описаний:
var s1: string[10]; (*строка длиной 10 символов*) s2: string; (*строка длиной 255 символов*)
Необходимо отметить, что один символ и строка длиной в один3) символ
var c: char; s: string[1];
совершенно не эквивалентны друг другу. Вне зависимости от своей реальной длины, строка относится к конструируемым структурированным типам данных, а не к базовым порядковым (см. лекцию 2).
Символ-константа и строка-константа
Неименованные константы
В тексте программы на языке Pascal последовательность любых символов, заключенная в апострофы, воспринимается как символ или строка. Например:
c:='z'; {c: char}
s:='abc'; {s: string}
Константе автоматически присваивается "минимальный" тип данных, достаточный для ее представления: char или string[k]. Поэтому попытка написать
c:='zzz'; {c: char}
вызовет ошибку уже на этапе компиляции.
Кроме того, не забывайте, что если константа длиннее той переменной-строки, куда ваша программа пытается ее записать, то в момент присваивания произойдет усечение ее до нужной длины.
Пустая строка задается двумя последовательными апострофами:
st:= '';
Если же необходимо сделать так, чтобы среди символов строки содержался и сам апостроф, его нужно удвоить:
s:='Don''t worry about the apostrophe!';
Если теперь вывести на экран эту строку, то получится следующее:
Don't worry about the apostrophe!
Нетипизированные константы
Все правила задания символов и строк как неименованных констант остаются в силе и при задании именованных нетипизированных констант в специальном разделе const. Например:
const c3 = ''''; {это один символ - апостроф!}
s3 = 'This is a string';
Типизированные константы
Типизированная константа, которая будет иметь тип char или string, задается в разделе const следующим образом:
const c4: char = ''''; {это один символ - апостроф!}
s4: string[20] = 'This is a string';
Действия с символами
Операции
Результатом унарной операции
#<положительная_неименованная_константа_целого_типа>
является символ, номер которого в таблице ASCII соответствует заданному числу. Например,
#100 = 'd'
#39 = '''' {апостроф}
#232 = 'ш'
#1000 = 'ш' {потому что (1000 mod 256)= 232}
Кроме того, к символьным переменным, как и к значениям всех порядковых типов данных, применимы операции сравнения <, <>, >, =, результат которых также опирается на номера символов из таблицы ASCII.
Стандартные функции
Функция chr(k:byte):char "превращает"; номер символа в символ. Действие этой функции аналогично действию операции #. Например:
c:= chr(48); {c: char}
{c = '0'}
Обратной к функции chr() является уже изученная нами функция ord(). Таким образом, для любого числа k и для любого символа с
ord(chr(k)) = k и chr(ord(c)) = c
Надеемся, читатель помнит, что стандартные процедуры и функции pred(), succ(), inc() и dec(), определенные для значений любого порядкового типа4), применимы также и к символам (значениям порядкового типа данных char). Например:
pred('[') = 'Z'
succ('z') = '{'
inc('a') = 'b'
inc('c',2) = 'e'
dec('z') = 'y'
dec(#0,4) = '№' {#252}
Стандартная функция upcase(c: char):char превращает строчную букву в прописную. Символы, не являющиеся строчными латинскими буквами, остаются без изменения (к сожалению, в их число попадают и все русские буквы).
Стандартные функции и процедуры обработки строк
Для обработки символьных массивов, которыми являются строки, в языке Pascal существуют специальные подпрограммы:
Функция concat(s1,_,sN:string):string осуществляет слияние (конкатенацию) всех перечисленных строк или символов в указанном порядке. Если длина итоговой строки больше 255-ти символов, то произойдет отсечение "хвоста". Кроме того, даже если результат конкатенации не был усечен, но программа пытается сохранить его в переменную заведомо меньшей длины, то усечение все равно состоится:
concat('abc','3de',' ','X','yz') = 'abc3de Xyz'-
Функция copy(s:string;i,k:byte):string вычленяет из строки s подстроку длиной k символов, начиная с i-го. Если i больше длины строки, то результатом будет пустая строка. Если же k больше, чем длина оставшейся части строки, то результатом будет только ее "хвост":
copy('abc3de Xyz',2,4) = 'bc3d' copy('abc3de Xyz',12,4) = '' copy('abc3de Xyz',8,14) = 'Xyz' -
Процедура delete(s:string;i,k:byte) удаляет из строки s подстроку длиной k символов, начиная с i-го. Если i больше длины строки, то ничего удалено не будет. Если же k больше, чем длина оставшейся части строки, то удален будет только ее "хвост":
{s = 'abc3de Xyz'} {s = 'abc3de Xyz'} delete(s,2,3); delete(s,8,13); {s = 'ade Xyz'} {s = 'abc3de '} -
Процедура insert(ss,s:string;i:byte) вставляет подстроку ss в строку s, начиная с i-го символа. Если i выходит за конец строки, то подстрока ss припишется в конец строки s (если результат длиннее, чем допускается для строки s, произойдет его усечение):
{s = 'abc3de Xyz'} {s = 'abc3de'} insert('xyz',s,2); insert('xyz',s,12); {s = 'axyzbc3de Xyz'} {s = 'abc3dexyz'} -
Функция length(s:string):byte возвращает длину строки s:
length('abc3de Xyz') = 10 -
Функция pos(ss,s:string):byte определяет позицию, с которой начинается первое (считая слева направо) вхождение подстроки ss в строку s. Если ss не встречается в s ни разу, функция вернет 0:
pos('abc3de Xyz','X') = 8 -
Процедура str(x[:w[:d]],s:string) превращает десятичное число x (можно указать, что в этом числе w цифр, из них d дробных) в строку s. Если число короче указанных величин, то спереди и/или сзади оно будет дополнено пробелами:
str(156.4:7:2,s); {s = ' 156.4 '} -
Процедура val(s:string;i:<арифметический_тип>;err:byte) превращает строку s в десятичное число x (в случае ошибки в переменную err будет записан номер первого недопустимого символа):
{s = '15.47'} val(s,x,err); {x = 15.47}
Операции со строками
Сравнения
Строки - это единственный структурированный тип данных, для элементов которого определен порядок и, следовательно, возможны операции сравнения (=, >, <).
На строках определен так называемый лексикографический порядок: из двух строк меньшей считается та, у которой первый различный символ меньше. Считается, что пустая строка меньше любой другой строки.
Таким образом, если начальные символы двух сравниваемых строк совпадают, то эта совпадающая часть никак не повлияет на отношение порядка между строками, поэтому ее можно откинуть и сравнивать только первые символы оставшихся подстрок. Если одна из строк полностью совпадает с началом другой, то после удаления совпадающих частей она превратится в пустую строку. Это с очевидностью будет свидетельствовать о том, что начало слова всегда меньше, чем все слово.
Итак,
'abc' < 'xyz' 'a' < 'abc' '1200' < '45' 'Anny' < 'anny'
Обращение к компонентам строки
Доступ к k-му символу строки осуществляется так же, как к k-й компоненте массива (жирные скобки являются обязательным элементом синтаксиса):
<имя_строки>[<индекс>]
Например:
{s = '15.47'}
c:= s[3];
{c = '.'}
Однако, в отличие от массива, нельзя напрямую заменять символы в строке, то есть действие
s[i]:= 'a';
не вызовет ошибки при компиляции, но, скорее всего, не станет работать во время выполнения программы. Для того чтобы изменить символ в строке, нужно воспользоваться стандартными функциями length(), concat() и copy(). В этом случае простое, казалось бы, действие приходится представлять как последовательность четырех операций:
В качестве первой подстроки взять из строки s символы с 1-го по (k-1)-й:
s1:= copy(s,1,k-1);
-
В качестве второй подстроки взять новое значение заменяемого символа:
s2:= new_char;
-
В качестве третьей подстроки взять оставшуюся часть строки s:
s3:= copy(s,k+1,length(s)-k);
-
Слить эти строки воедино, а результат записать вместо исходной строки s:
s:= concat(s1,s2,s3);
Или можно объединить все четыре действия в одном операторе:
s:= concat(copy(s,1,k-1), new_char, copy(s,k+1,length(s)-k));
Конкатенация
Единственная операция, которую разрешается производить с переменными строкового типа, - это слияние строк или символов (конкатенация). Она полностью эквивалентна функции concat() и записывается при помощи знака "+". Таким образом, предыдущий оператор можно сделать более простым:
s:= copy(s,1,k-1) + new_char + copy(s,k+1,length(s)-k);
Множества
Еще один структурированный тип данных - это множество (set). В нем может содержаться не более 256 элементов.
Важное отличие множества от остальных структурированных типов состоит в том, что его элементы не являются упорядоченными.
Описание множеств
В разделе var множества описываются следующим образом:
var <имя_множества>: set of <тип_элементов_множества>;
Элементы могут принадлежать к любому порядковому типу, размер которого не превышает 1 байт (256 элементов). Например:
var s1: set of char; {множество из 256-ти элементов}
s2: set of 'a'..'z','A'..'Z'; {множество из 52-х элементов}
s3: set of 0..10; {множество из 11-ти элементов}
s4: set of boolean; {множество из 2-х элементов}
Множество-константа
Неименованная константа
Множество можно задать неименованной константой прямо в тексте программы. Для этого необходимо заключить список элементов создаваемого множества в квадратные скобки:
[<список_элементов>]
Список элементов может быть задан перечислением элементов нового множества через запятую, интервалом или объединением этих двух способов. Элементы и границы интервалов могут быть переменными, константами и выражениями. Если левая граница интервала окажется больше правой, результатом будет пустое множество.
Примеры конструирования и использования различных множеств:
if c in ['a','e','i','o','u']
then writeln('Гласная буква');
if set1 < [k*2+1..n,13] then set1:=[];
Нетипизированная константа
Множество - это структурированный тип данных, поэтому его невозможно задать нетипизированной константой.
Типизированная константа
Задать множество как типизированную константу можно в разделе const:
<имя_константы> : set of <тип_элементов> =[<список_элементов>];
Например:
type cipher = set of '0'..'9'; const odds: cipher = ['1','3','5','7','9']; vowels: set of 'a'..'z' = ['a','o','e','u','i'];
Операции с множествами
Все теоретико-множественные операции реализованы и в языке Pascal:
| 1) Пересечение двух множеств s1 и s2: | s:=s1*s2; |
| 2) Объединение двух множеств s1 и s2: | s:=s1+s2; |
| 3) Разность двух множеств s1 и s2 (все элементы, которые принадлежат множеству s1 и одновременно не принадлежат множеству s2)5): | s:=s1-s2; |
| 4) Проверка принадлежности элемента el множеству s (результат этой операции имеет тип boolean): | el in s |
| 5) Обозначение для пустого множества: | [] |
| 6) Создание множества из списка элементов: | s:=[e1,_,eN]; |
| 7) Проверка двух множеств на равенство или строгое включение (результат этих операций имеет тип boolean): | s1 = s2 s1 > s2 s1 < s2 |
Не существует никакой процедуры, позволяющей распечатать содержимое множества. Это приходится делать следующим образом:
{s: set of type1; k: type1}
for k:= min_type1 to max_type1
do if k in s then write(k);
Представление множеств массивами
Одно из основных неудобств при работе с множествами - это ограничение размера всего лишь 256-ю элементами. Мы приведем здесь два очень похожих способа представления больших множеств массивами. Единственным условием является наличие некоторого внутреннего порядка среди представляемых элементов: без этого невозможно будет их перенумеровать.
Представление множеств линейными массивами
Задав линейный массив достаточной длины, можно "вручную" сымитировать множество для более широкого, чем 256 элементов, диапазона значений. Например, чтобы работать с множеством, содержащим 10 000 элементов, достаточно такого массива:
set_arr: array[1..10000] of boolean;
При таком способе представления возможно задать множество до 65 000 элементов.
Для простоты изложения мы ограничимся только числовыми множествами, однако все сказанное ниже можно применять и к множествам, элементы которых имеют другую природу. Итак, признаком того, что элемент k является элементом нашего множества, будет значение true в k-й ячейке этого массива.
Посмотрим теперь, какими способами мы вынуждены будем имитировать операции над "массивными" множествами.
Проверка множества на пустоту может быть осуществлена довольно просто:
pusto:= true; for i:= 1 to N do if set_arr[i] then begin pusto:= false; break end;-
Проверка элемента на принадлежность множеству также не вызовет никаких затруднений, поскольку соответствующая компонента массива содержит ответ на этот вопрос:
is_in:= set_arr[element];
-
Добавление элемента в множество нужно записывать так:
set_arr[element]:= true;
-
Удаление элемента из множества записывается аналогичным образом:
set_arr[element]:= false;
-
Построение пересечения множеств реализуется как проверка вхождения каждого элемента в оба множества и последующее добавление удовлетворивших этому условию элементов в результирующее множество.
-
Построение объединения множеств аналогичным образом базируется на проверке вхождения элемента хотя бы в одно из объединяемых множеств и дальнейшем добавлении элементов в результирующее множество.
-
Построение разности двух множеств также опирается на проверку вхождения элемента в оба множества, причем добавление элемента в создаваемое множество происходит только в том случае, если элемент присутствует в множестве-уменьшаемом и одновременно отсутствует в множестве-вычитаемом.
-
Проверка двух множеств на равенство не требует особых пояснений:
equal:= true; for i:=1 1 to N do if set1[i]<> set2[i] then begin equal:= false; break end; -
Проверка двух множеств на включение (set1<set2) тоже не потребует больших усилий:
subset:= true; for i:= 1 to N do if set1[i]and not set2[i] then begin subset:= false; break end;
Представление множеств битовыми массивами
В случае, если 65 000 элементов недостаточно для задания всех необходимых множеств (например, 10 множеств по 10 000 элементов в каждом), это число можно увеличить в 8 раз, перейдя от байтов к битам. Тогда 1 байт будет хранить информацию не об одном, а сразу о восьми элементах: единичный бит будет означать наличие элемента в множестве, а нулевой бит - отсутствие.
Задавая битовый массив, начнем нумерацию его компонент с 0:
set_bit: array[0..N-1] of byte;
Тогда результатом операции <номер_элемента> div 8 будет номер той компоненты массива, в которой содержится информация об этом элементе. А вот номер бита, в котором содержится информация об этом элементе, придется вычислять более сложным образом:
bit:= <номер_элемента> mod 8; if bit=0 then bit:= 8;
Эти вычисления потребуются нам еще не раз, поэтому запишем их снова, более строго, а затем будем использовать по умолчанию (element - это "номер" обрабатываемого элемента в нашем множестве):
kmp:= element div 8; {номер компоненты массива}
bit:= element mod 8; {номер бита}
if bit=0 then bit:= 8;
Перечислим теперь действия, которые потребуются для реализации операций над множествами, заданными битовыми массивами.
Проверка множества на пустоту почти не будет отличаться от аналогичной проверки в случае представления множества не битовым, а обычным массивом:
pusto:= true; for i:= 0 to N-1 do if set_arr[i]<>0 then begin pusto:= false; break end;-
Проверка элемента на принадлежность множеству потребует несколько большей изворотливости ведь нам теперь нужно вычленить соответствующий бит:
if set_arr[kmp]and(1 shl(bit-1))=0 then is_in:= false else is_in:= true;Поясним, что здесь используется операция "побитовое и" (см. лекцию 2), которая работает непосредственно с битами нужной нам компоненты массива и числа, состоящего из семи нулей и единицы на месте с номером bit.
-
Добавление элемента в множество теперь будет записано так:
set_arr[kmp]:= set_arr[kmp]or(1 shl(bit-1));
Здесь нельзя использовать обычную операцию сложения (+), так как если добавляемый компонент уже содержится в множестве (то есть соответствующий бит уже имеет значение 1), то в результате сложения 1+1 получится 10: единица автоматически перенесется в старший бит, а на нужном месте окажется 0.
-
Удаление элемента из множества придется записать более сложным образом:
set_arr[kmp]:= set_arr[kmp]and not(1 shl(bit-1));
Операция not превратит все 0 в 1 и наоборот, следовательно, теперь в качестве второго операнда для побитового and будет фигурировать число, состоящее из семи единиц и нуля на месте с номером bit. Единицы сохранят любые значения тех битов, которые должны остаться без изменения, и лишь 0 "уничтожит" значение единственного нужного бита.
-
Пересечение множеств реализуется теперь при помощи операции "побитовое и":
for i:= 0 to N-1 do set_res[i]:= set1[i] and set2[i];
-
Объединение множеств реализуется при помощи операции "побитовое или":
for i:= 0 to N-1 do set_res[i]:= set1[i] or set2[i]; -
Разность двух множеств может быть построена так:
for i:= 0 to N-1 do set_res[i]:= (set1[i] or set2[i]) and not set2[i];Поясним, что здесь мы вначале прибавляем содержимое второго множества к первому, чтобы затем быть полностью уверенными в правомерности операции вычитания.
-
Проверка двух множеств на равенство по-прежнему не требует особых пояснений:
equal:= true; for i:=0 to N-1 do if set1[i]<> set2[i] then begin equal:= false; break end; -
Проверка двух множеств на включение (set1<set2) будет производиться по схеме: "Если (A\B)
B=A, то B
A ", доказательство которой настолько очевидно, что мы не станем на нем задерживаться:subset:= true; for i:= 0 to N-1 do if((set1[i] or set2[i])and not set2[i]) or set2[i] <> set1[i] then begin subset:= false; break end;
Замечание. Если предстоит многократно выполнять действия с элементами битовых массивов, то используемые для этого значения "единиц" удобнее всего сразу задать в специальном массиве:
{ed: array[1..8] of byte;}
ed[1]:=1;
for k:= 2 to 8 do
ed[k]:= ed[k-1] shl 1;
И далее вместо громоздкой конструкции 1 shl(bit-1) можно использовать просто ed[bit].
Примеры использования символов, строк и множеств
Задача 1. Оставить в строке только первое вхождение каждого символа, взаимный порядок оставленных символов сохранить.
program z1;
var s: set of char;
inp, res: string;
i: byte;
begin
s:=[];
res:= '';
for i:= 1 to length(inp) do
if not(inp[i] in s)
then begin res:= res+inp[i];
s:= s+[inp[i]];
end;
end.
Задача 2.6) Оставить в строке только последнее вхождение каждого символа, взаимный порядок оставленных символов сохранить.
program z2;
var inp, res: string;
i: byte;
begin
res:= '';
for i:= 1 to length(inp) do
begin
k:= pos(inp[i],res);
if k<>0
then delete(res,k,1);
res:= res+inp[i];
end;
end.
Задача 3. Выдать первые 100 000 натуральных чисел в случайном порядке без повторений.
program z3;
var bset: array[0..12499] of byte; {множество, битовый
массив}
ed: array[1..8] of byte;
el,k: longint;
kmp,bin: integer;
begin
ed[1]:= 1; {генерация массива
битовых единиц}
for k:= 2 to 8 do ed[k]:= ed[k-1] shl 1;
{-------------------------------------------------------}
k:=0;
randomize; {процедура активизации генератора случайных
чисел}
while k<100000 do
begin
el:= 1+random(99999); {случайное число из диапазона 0..99999}
kmp:= el div 8;
bit:= el mod 8;
if bit=0 then bit:= 8;
if bset[kmp]and ed[bit]=0 {проверка повторов}
then begin inc(k);
writeln(el);
bset[kmp]:= bset[kmp]or ed[bit]
end;
end
end.
 |
|
|
2) Напомним, что жирная квадратная скобка является стандартным элементом синтаксиса, а обычная - указанием на необязательность заключенных в нее элементов.
3) На самом деле "строка длиной в один символ" имеет две компоненты: s[0] (длина строки = 1) и s[1] (собственно символ)
4) См. лекцию 2.
5) Если множества s1 и s2 не пересекаются, то результат s будет совпадать с s1.
6) Более простой вариант решения - повторить решение задачи 1 с заменой цикла for-to на for-downto. Приведенный же вариант решения можно использовать для обработки не только строк, но и файлов.