comp-science.narod.ru ==> Дидактические материалы по информатике ==> Поиск и сортировка в одномерных массивах

Поиск и сортировка в одномерных массивах

Поиск

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

Алгоритм носит название двоичного (бинарного) поиска, т.к. на каждом шаге область поиска уменьшается вдвое.

Пусть в отсортированном массиве требуется найти элемент со значением x, или указать, что такого элемента там нет. Выберем средний элемент. Для этого элемента относительно значения x возможны три случая:

1. элемент равен x (поиск завершен);
2. элемент больше x (поиск необходимо продолжить в левой части массива);
3. элемент меньше x (поиск необходимо продолжить в правой части массива).

В случаях 2-3 поиск (если это ещё возможно) продолжается. Для этого в выделенной части массива вновь выбирается средний элемент и проводятся аналогичные рассуждения. И т.д., до тех пор, пока поиск не будет завершен.

Поиск завершается в одном из двух случаев:

1. элемент найден;
2. элемент не найден (это констатируется в том случае, когда длина области поиска уменьшилась до нуля, т.е. левая и правая границы области поиска сомкнулись).

Рассмотрим программную реализацию алгоритма.

{Алгоритм двоичного поиска}
type mas= array[1..100] of integer;

{Процедура вывода массива}
Procedure Print(n: byte; const a: mas);
Var i: byte;
Begin
	For i := 1 to n do
		write(a[i] :8);
	writeln
End;

{Процедура формирования массива из случайных элементов, расположенных по возрастанию}
Procedure Vvod_Sl(var n: byte; var a: mas);
Var i: byte;
Begin
	Write(‘Количество элементов?’); Readln(n);
	a[1]:= -1000+random(2001);
	For i := 2 to n do
		a[i] := a[i-1]+random(20)+1;
End;

function find(a: mas; n: byte; x: integer): byte;
var L, R, c: byte;
Begin L := 1; R := n; {изначально область поиска - весь массив}
repeat
     c := (L + R) div 2; {индекс среднего элемента}
     if a[c] > x then R := c - 1; {случай 2}
     if a[c] < x then L := c + 1; {случай 3}
until (a[c]=x) or (L > R);
if a[c]=x then find:=c else find := 0; {возвращем индекс элемента или нуль, если элемент не найден}
end;

var a: mas; n, r: byte;  k: integer;
begin   randomize;
	Vvod_Sl(n, a);
	print(n, a);
    	write('Искомый элемент? '); readln(k);
	r := find(a, n, k);   
	if r = 0 then writeln('Элемент не найден') else writeln(r)
end.

Сортировка

Обычно сортировку подразделяют на два класса: внутреннюю и внешнюю. При внутренней сортировке все элементы хранятся в оперативной памяти, таким образом, как правило, это сортировка массивов. При внешней сортировке — элементы хранятся на внешнем запоминающем устройстве, это сортировка файлов.

Одно из Основных требований к методам сортировки — экономное использование памяти. Это означает, что переупорядочение нужно выполнять «на том же месте», то есть методы пересылки элементов из одного массива в другой не представляют интереса.

Удобной мерой эффективности является подсчет числа С — сравнений элементов и М — присваиваний элементов. Достаточно хороший алгоритм затрачивает на сортировку N элементов время порядка N×log₂(N). Простейшие алгоритмы сортировки, которые мы рассмотрим в этом разделе, обладают характеристикой порядка N². Если N достаточно мало, то простые алгоритмы выгодно использовать в силу простоты их реализации.

Сортировка выбором

Алгоритм сортировки. Пусть часть массива до i-1 элемента включительно отсортирована. Выбираем в не сортированной части минимальный элемент и меняем его местами с i-м.

Изначально отсортированная часть состоит из нулевого количества элементов.

procedure sort(var a : mas; n : byte);
var i, j, min: byte; vsp : integer;
begin
     for i := 1 to n - 1 do
     begin
         min:=i;
         for j := i+1 to n do
                 if a[j]<a[min] then min := j;
         vsp:=a[i]; a[i]:=a[min]; a[min]:=vsp;
     end;
end;

Сортировка обменом (пузырьковая)

Массив просматривается N-1 раз. При каждом просмотре сравниваются каждые два соседних элемента. Если элемент с меньшим индексом оказывается больше, производится их обмен.

procedure obmen(var a : mas; n : byte);
var i, j: byte; vsp : integer;
begin
     for i := 1 to n - 1 do
       for j := 1 to n - i do
         if a[j]>a[j+1] then
         			begin
					vsp:=a[j];
					a[j]:=a[j+1];
					a[j+1]:=vsp;
				end
end;

Сортировка вставками

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

procedure vstavka(var a : mas; n : byte);
var i, j: byte; vsp : integer;
begin
     for i := 2 to n do
     begin vsp:=a[i];
           j:= i-1;
           while (a[j]>vsp) and (j>1) do
           begin
		a[j+1]:=a[j];
		j:=j-1
	   end;
           if (a[j]>vsp) and (j=1)
           then begin
			a[2]:=a[1];
			a[1]:= vsp
		end
	   else a[j+1]:=vsp;
     end
end;