Лекция 2
Реализация
Реализацию
// Коды для сортировки
вставками
typedef int T; /*
Тип элемента, который нужно сортировать */
typedef int tblIndex; /* Тип
ключа сортировки */
#define compGT(a,b) (a > b)
void insertSort(T *a, tblIndex lb,
tblIndex ub) {
T t;
tblIndex i, j;
/**********************************
* Сортировка
массива a[lb..ub] *
**********************************/
for (i = lb + 1; i <= ub; i++) {
t = a[i];
/* Элементы сдвигаются вниз до */
/* найденного места вставки. */
for (j = i-1; j >= lb && compGT(a[j], t); j--)
a[j+1] =
a[j];
/* Вставка */
a[j+1] = t;
}
}
Дополнительно
Здесь рассмотрим более подробно группу
простых методов сортировки. Кроме того в этом разделе мы будем рассматривать
программы сортировок в нотации языка Pascal. Поэтому некоторые
методы основного раздела могут здесь быть рассмотрены повторно. Итак…
Основное требование к методам сортировки массивов – экономное
использование памяти. Это означает, что переупорядочение элементов нужно
выполнять in situ (на том же месте) и что методы, которые пересылают элементы
из массива A в массив B, пока не представляют для нас интереса. Таким образом,
выбирая метод сортировки, классификацию алгоритмов удобно проводить в
соответствии с их эффективностью, т.е. экономией времени или быстродействием.
Удобная мера эффективности получается при подсчете числа С необходимых сравнений ключей и М пересылок элементов. Эти числа определяются некоторыми функциями
от числа n сортируемых элементов.
Хотя хорошие алгоритмы сортировки требуют порядка (n*log(n))сравнений,
мы сначала обсудим несколько несложных и очевидных способов сортировки,
называемых простыми методами, которые требуют порядка n^2 сравнений ключей.
Изучение простых методов важно по следующим причинам:
Методы, сортирующие in
situ, можно разбить на три основных класса в зависимости от лежащего в их
основе приема:
Теперь рассмотрим и сравним эти три принципа. Программы
работают с массивом A, компоненты которой нужно рассортировать in situ,в этих программах
используются типы данных item и index, определенные так:
type
index = 0 .. n;
var A: array [1 .. n] of
item;
Сортировка включениями
Сортировка включениями (то
же, что вставками) есть общее название группы методов сортировки,
основанных на последовательной вставке "новых” элементов в увеличивающийся упорядочиваемый
список. Простейшим методом является линейная вставка.
Сортировка простыми включениями
Этот метод обычно используют игроки в карты. Элементы (карты) условно
разделяются на готовую последовательность A[1],...,A[i-1] и входную
последовательность A[i],...,A[n]. На каждом шаге, начиная с i=2 и увеличения i
на единицу, берут первый элемент входной последовательности и передают в
готовую последовательность, вставляя его на подходящее место.
Пример сортировки "просеивание”.
начальные ключи 44 55 12 42 94 18 06 67
i=2 44 55 12 42 94 18 06 67
i=3 12 44 55 42 94 18 06 67
i=4 12 42 44 55 94 18 06 67
i=5 12 42 44 55 94 18 06 67
i=6 12 18 42 44 55 94 06 67
i=7 06 12 18 42 44 55 94 67
i=8 06 12 18 42 44 55 67 94
Процесс сортировки включениями показан на примере восьми
случайно взятых чисел. Алгоритм
сортировки простыми включениями
выглядит следующим образом:
for i:= 2 to n do
begin x:= A[i]
"вставить х на подходящем месте в A[1]...A[i]"
end
При поиске подходящего места чередовать сравнения и пересылки,
т.е. как бы "просеивать" х, сравнивая его с очередным элементом A[j] и
либо вставляя х, либо пересылая A[j] направо и продвигаясь налево. Заметим, что
"просеивание" может закончиться при двух различных условиях:
Найти элемент A[j] с ключом меньшим, чем ключ х.
Достигнут левый конец
готовой последовательности.
Этот типичный пример цикла с двумя условиями окончания дает нам
возможность рассмотреть хорошо известный прием фиктивного элемента ("барьера").
Его можно легко применить в этом случае, установив барьер A[0] = х. (Заметим,
что для этого нужно расширить диапазон индексов в описании A до 0,...,n).
Окончательный алгоритм представлен ниже в виде программы.
Реализация
procedure StraightInsertion;
var i,j: index; x:
item;
begin
for
i:= 2 to n do
begin
x:= A[i]; A[0]:= x; j:= i-1
while (x.key < A[j].key) do
begin
A[j+1]:=A[j]; j:=j-1;
end;
A[j+1]:=x;
end;
end;
Сортировка бинарными включениями
Алгоритм сортировки простыми включениями легко улучшить, если обратить
внимание на то, что готовая последовательность A[1],...,A[i],в которую
требуется включить новый элемент, уже упорядочена. Место включения можно найти
значительно быстрее, если применить бинарный поиск. Модифицированный алгоритм
сортировки называется сортировкой бинарными включениями, он приведен ниже в
программе.
Реализация
procedure BinaryInsertion;
var i,j,l,r,m: index; x: item;
begin
for
i:= 2 to n do
begin x:=A[i]; l:=1; r:=i-1;
while (l<=r) do
begin
m:=(l+r) div 2;
if
(x.key<A[m].key) then r:=m-1 else l:=m+1;
end;
for j:=i-1 downto l do A[j+1]:=a[j];
A[l]:=x;
end;
end;
Сортировка выбором
Линейный выбор
Прямой линейный выбор является не минимальным по памяти методом.
Один просмотр в линейном выборе включает выбор из сортируемого списка
элемента с наименьшим ключом и размещение его в формируемом списке вывода. Просмотры
выполняются до тех пор, пока список вывода не будет сформирован полностью. В
готовом виде список вывода представляет собой упорядоченный исходный список. В
начале каждого просмотра первый элемент списка считается элементом с наименьшим
ключом. Ключ и адрес этого элемента передаются в рабочую память, где ключ
сравнивается с ключом второго элемента. Если первый ключ меньше, то он
сравнивается с ключом третьего элемента и т.д. Он сравнивается со всеми
линейными преемниками до тех пор, пока в списке не найдется меньший элемент.
Затем ключ найденного наименьшего элемента вместе с его адресом заменяет в
рабочей памяти находившиеся там ключ и адрес и участвует в последующих
проверках.
Ключ наименьшего на данный момент времени элемента всегда
расположен в рабочей памяти и используется при сравнениях с оставшимися в
списке ключами. По достижению конца списка наименьший элемент известен, так как
это именно тот элемент, чей ключ и адрес находится в рабочей памяти. Затем этот
элемент передается их исходного списка в текущую позицию области вывода. В
исходном списке ключ каждого перемещенного элемента заменяется фиктивной величиной
(например, полем из одних девяток), превосходящей любой ключ в списке, для
того, чтобы предотвратить повторный выбор этого элемента.
То, что адрес выбранного элемента находится в рабочей памяти,
позволяет определять не только его место при пересылке, но и место, куда
следует поместить фиктивный ключ. Если поле ключа является одновременно и полем
элемента, то пересылка в список вывода может выполняться непосредственно из
рабочей памяти, так как в ней находится вся запись. При каждом просмотре в
список вывода добавляется текущий наименьший член сортируемого списка. Первый
просмотр добавляет наименьший элемент, второй просмотр- следующий наименьший и
т.д.. Таким образом, в области вывода формируется упорядоченный список.
Сортировка заканчивается, когда все члены исходного списка окажутся в списке
вывода.
Линейный выбор с обменом
Этот метод основан на следующем правиле:
Эти операции затем повторяются с оставшимися n-1 элементами,
затем с n-2 элементами, пока не останется только один элемент - наибольший. Этот
метод продемонстрирован на тех же восьми ключах:
i=4
06 12 18 42 94 55 44 67 (42 уже на месте)
i=6 06
12 18 42 44 55 94 67 (55 уже на месте)
i=8 06
12 18 42 44 55 67 94
Программу можно представить следующим образом:
for i:= 1 to n-1 do
begin "присвоить k индекс наименьшего элемента из A[i] ...A[n]”
"поменять местами A[i] и A[k]"
end
Этот метод, называемый сортировкой простым выбором, в некотором
смысле противоположен сортировке простыми включениями. При сортировке простыми
включениями на каждом шаге рассматривается только один очередной элемент
входной последовательности и все элементы готового массива для нахождения места
включения. При сортировке простым выбором рассматриваются все элементы входного массива для нахождения
элемента с наименьшим ключом, и этот один очередной элемент отправляется в
готовую последовательность. Весь алгоритм сортировки простым выбором представлен
в виде программы ниже.
Реализация
procedure StraightSelection;
var i,j,k: index; x: item;
begin for i:= 1 to n-1 do
begin k:= i; x:= A[i];
for j:= i+1 to n do
if (A[j].key < x.key) then
begin k:= j; x:= A[j];
end;
A[k]:= A[i]; A[i]:= x;
end;
end;
|