 |
Сортировка массивов
|
|
|
|
Простейшая задача сортировки заключается в упорядочении элементов массива по возрастанию или убыванию. Другой задачей является упорядочение элементов массива в соответствии с некоторым критерием. Обычно в качестве такого критерия выступают значения определенной функции, аргументами которой выступают элементы массива. Эту функцию принято называть упорядочивающей функцией.
Сортировка обменом (методом "пузырька")
Идея метода заключается в том, что последовательно сравниваются пары соседних элементов массива. Если они располагаются не в том порядке, то совершаем перестановку, меняя местами пару соседних элементов. После одного такого прохода на последнем месте номер N окажется максимальный элемент ("всплыл" первый "пузырек"). Следующий проход должен рассматривать элементы до предпоследнего и так далее. Всего требуется N-1 проход. Вычислительная сложность сортировки обменом O(N*N).
ПРИМЕР: Сортировка по возрастанию массива A из N целых чисел. (Базовый вариант)
program Sort_Obmen1;
var A: array [1..100] of integer;
N,i,k,x: integer;
Begin
write ('количество элементов массива ');
read (N);
for i:=1 to n do read (A[i]);
for k:=n-1 downto 1 do { k - количество сравниваемых пар }
for i:=1 to k do
if A[i]>A[i+1] then
{меняем местами соседние элементы}
begin x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x; end;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end.
Можно заметить, что если при выполнении очередного прохода в сортировке обменом не произведено ни одной перестановки, то это означает, что массив уже упорядочен. Таким образом, можно модифицировать алгоритм, чтобы следующий проход делался только при наличии перестановок в предыдущем.
ПРИМЕР: Сортировка обменом с проверкой факта перестановки.
|
|
|
program Sort_Obmen2;
var A: array [1..100] of integer;
N,i,k,x: integer; p:boolean;
Begin
write ('количество элементов массива ');
read (N);
for i:=1 to n do read (A[i]);
k:=n-1; {количество пар при первом проходе}
p:=true; {логическая переменная p истинна, если были перестановки, т.е. нужно продолжать сортировку}
while p do
Begin
p:=false;
{Начало нового прохода. Пока перестановок не было.}
for i:=1 to k do
if A[i]>A[i+1] then
Begin
x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x; {меняем элементы местами}
p:=true; {и запоминаем факт перестановки}
end;
k:=k-1; {уменьшаем количество пар для следующего прохода}
end;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end.
Следующая модификация алгоритма сортировки обменом получается при запоминании места последней перестановки. Если при очередном проходе последней парой элементов, которые поменялись местами, были A[i] и A[i+1], то элементы массива с i+1 до последнего уже стоят на своих местах. Использование этой информации позволяет нам сделать количество пар для следующего прохода равным i-1.
ПРИМЕР: Сортировка обменом с запоминанием места последней перестановки.
program Sort_Obmen3;
var A: array [1..100] of integer;
N,i,k,x,m: integer;
Begin
write ('количество элементов массива ');
read (N);
for i:=1 to n do read (A[i]);
k:=n-1; {количество пар при первом проходе}
while k>0 do
Begin
m:=0;
{пока перестановок на этом проходе нет, место равно 0}
for i:=1 to k do
if A[i]>A[i+1] then
Begin
x:=A[i]; A[i]:=A[i+1]; A[i+1]:=x; {меняем элементы местами}
m:=i; {и запоминаем место перестановки}
end;
k:=m-1; {количество пар зависит от места последней перестановки}
end;
for i:=1 to n do write (A[i],' '); {упорядоченный массив}
end.
|
|
|
Внутренняя сортировка
Какие команды используются для описания массивов? Объяснить действия команд обмена данными (между базой данных и массивами).
Копирование, поиск и сортировка записей.
Листинг 18.6. Класс массивов с локализацией ошибок
Медицинская сортировка пораженных в ЧС
Мойка зерен. Сортировка по качеству и размеру
Поиск, сортировка данных
Применение методики «Сортировка цветных фигур» в коррекционно-развивающем обучении
Пример 11. Сортировка по значениям одного столбца
Сортировка белков в аппарате Гольджи
