Организация поиска и сортировки в массивах

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

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

      Дан отсортированный по возрастанию массив  вещественных  чисел  A состоящий из n элементов.  Определить, содержит ли данный массив число B, и если содержит,  то определить номер (индекс) данного  элемента  в массиве.

      Алгоритм поиска элемента делением пополам обладает высоким  быстродействием.  Вообще  идея деления пополам (сведение задачи примерно к вдвое более простой в количественном отношении) оказывается весьма плодотворной  для построения многих алгоритмов.  Для обозначения сущности идеи алгоритма часто применяют выражение "разделяй и властвуй".

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

Пусть есть упорядоченный  по возрастанию массив целых чисел. Нужно определить, содержит ли этот массив некоторое число (образец).

Метод (алгоритм) бинарного поиска реализуется  следующим образом:

1. Сначала образец  сравнивается со средним (по  номеру) элементом массива.

Если образец  равен среднему элементу, то задача решена.

Если образец  больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое  значение verb принимается sred+i, а значение niz не меняется.

Если образец  меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется.

2. После того  как определена часть массива,  в которой может находиться искомый элемент, по формуле (niz-verh) /2+verh вычисляется новое значение sred и поиск продолжается.

 

Практическая  часть работы

Пример №1 {Сортировка массива по возрастанию  методом прямого выбора }

program sortarr;

const

     SIZE=5;

var

     a:array[1..SIZE] of integer;

     i:integer;                 { номер элемента, от которого ведется поиск }

                                    { минимального эл-та }

     min:integer;            { номер минимального элемента  в части }

                                    { массива от i до верхней границы массива }

     j:integer;                 { номер эл-та, сравниваемого с  минимальным }

     buf:integer;             { буфер, используемый при обмене  эл-тов массива

     k:integer;

begin

     writeln('Сортировка массива.');

     write('Введите',SIZE:3,' целых в одной  строке ');

     writeln('через пробел и нажмите  <Enter>');

     for k:=1 to SIZE do read(a[k]);

 

     writeln('Сортировка');

     for i:=1 to SIZE-1 do

     begin      { поиск минимального эл-та в части массива от a[i] до a[SIZE]}

          for j:=i+1 to SIZE do begin

               if a[j]<a[i] then                { поменяем местами a[j] и a[i] }

              begin

 buf:=a[i];

               a[i]:=a[j];

               a[j]:=buf;

end;

          {выведем массив }

          for k:=1 to SIZE do write(a[k],' ');

          writeln;

                 end;     end;     writeln('Массив отсортирован.'); end.

 

Пример №2{ Сортировка массива целых по возрастанию  методом "пузырька" }

program sortarr1;

const

     SIZE=5;

var

        a:array[1..SIZE] of integer;

        i:integer;                  { счетчик циклов }

        k:integer;                  { текущий индекс элемента массива }

        buf:integer;

begin

     writeln('Сортировка массива методом "пузырька".');

     write('Введите',SIZE:3,' целых в одной строке через пробел ');     writeln ('и нажмите <Enter>');

     for k:=1 to SIZE do read(a[k]);

 

     writeln('Сортировка.');

     for i:=1 to SIZE-1

     do begin

          for k:=1 to SIZE-1

          do begin

               if a[k]>a[k+1]

               then begin                         { обменяем k-й и (k+1)-й элементы }

                    buf:=a[k];

                    a[k]:=a[k+1];

                    a[k+1]:=buf;

               end;

          end;

          for k:=1 to SIZE do write(a[k],' ');

          writeln;

     end;

     writeln('Массив отсортирован.');

end.

Пример №3 { Поиск в массиве  методом перебора элементов }

program poisk;

var

     massiv:array[1..10] of integer;           { массив целых}

     obrazec:integer;                                               { образец для поиска }

     naiden:boolean;                                                { признак совпадения с образцом }

     i:integer;

begin

     { ввод 10 целых чисел }

     writeln('Поиск в массиве.');

     write('Введите  10 целых в одной строке через  пробел ');

     writeln ('и нажмите <Enter>');

     write('->');

     for i:=1 to 10 do read(massiv[i]);

     { числа введены в массив }

     write('Введите  образец для поиска (целое число)-> ');

     readln(obrazec);

     { поиск простым перебором }

     naiden:=FALSE;                                                 { совпадений нет }

     i:=1;                                                                     { проверяем с первого элемента массива }

     repeat

          if massiv[i] = obrazec

               then naiden:=TRUE                   { совпадение с образцом }

               else i:=i+1;                        { переход к следующему элементу }

     until (i>10) or (naiden);                { завершим, если совпадение с образцом или проверено                                                                                                                 { последний элемент массива }

     if naiden

          then writeln('Совпадение с элементом номер', i:3,'. ')

          else writeln('Совпадений с образцом  нет.');

end.

Пример №4 { Бинарный поиск в упорядоченном массиве }

program poisk1;

var

     a:array[1..9] of integer;                        { массив целых }

     obrazec:integer;                                    { образец для поиска }

     sred,verh,niz:integer;                           { номера среднего, верхнего и  нижнего}

                                                                 { эл-тов массива}

     naiden:boolean;                                   { признак совпадения с образцом }

     n:integer;                                             { счетчик сравнений с образцом }

     i:integer;

begin

     { ввод 9 целых чисел }

     writeln('Бинарный  поиск в массиве.');

     write('Введите  9 целых в одной строке через  пробел ');

        writeln('и нажмите <Enter>');

     for i:=1 to 9 do read(a[i]); { здесь числа в массив введены }

Здесь необходимо вставить любой алгоритм сортировки массива                                                    writeln('Введите образец для поиска (целое число) ');

     readln(obrazec);

     { бинарный поиск }

     verh:=1;

     niz:=9;

     naiden:=FALSE;

     n:=0;

     writeln(' verh  niz   sred');

     repeat

          sred:=(niz-verh) div 2+verh;

          writeln(verh:5,niz:5,sred:5);

          n:=n+1;

          if a[sred]=obrazec then naiden:=TRUE

          else begin

               if obrazec<a[sred]

                    then niz:=sred-1

                    else verh:=sred+1;

          end;

     until (verh>niz) or naiden;

     if naiden

          then write('Совпадение с элементом  номер ',

                      sred,'. Выполнено ',n,' сравнений.')

          else writeln('Образец в массиве не  найден.');

        readln;

end.

 

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ:

Задание №1

Выполнить сортировку массива двумя способами: методом  прямого выбора и методом обмена. Ввод элементов массива организовать способом, указанным в варианте  задания.

№ варианта	Количество  элементов	Метод прямого выбора		Метод обмена
		Организация ввода	Вид сортировки	Организация ввода	Вид сортировки
1	6	Ввод с клавиатуры	По возрастанию	Датчик случайных  чисел	По убыванию
2	8	Ввод с клавиатуры	По убыванию	Через константы	По возрастанию
3	10	Датчик случайных  чисел	По возрастанию	Ввод с клавиатуры	По убыванию
4	5	Ввод с клавиатуры	По убыванию	Через константы	По возрастанию
5	12	Датчик случайных  чисел	По возрастанию	Через константы	По убыванию
6	11	Через константы	По убыванию	Ввод с клавиатуры	По возрастанию
7	15	Датчик случайных чисел	По возрастанию	Через константы	По убыванию
8	9	Через константы	По убыванию	Ввод с клавиатуры	По возрастанию
9	16	Через константы	По возрастанию	Датчик случайных  чисел	По убыванию
10	20	Датчик случайных  чисел	По убыванию	Через константы	По возрастанию
11	25	Датчик случайных  чисел	По возрастанию	Через константы	По убыванию
12	10	Через константы	По убыванию	Датчик случайных  чисел	По возрастанию
13	7	Ввод с клавиатуры	По возрастанию	Датчик случайных  чисел	По убыванию
14	11	Через константы	По убыванию	Ввод с клавиатуры	По возрастанию
15	14	Через константы	По возрастанию	Датчик случайных  чисел	По убыванию

 

 

Задание №2

Выполнить  бинарный поиск и  поиск методом перебора   числа n (n-ваш номер варианта)  для массива, состоящего из n+50 (n-ваш номер варианта) элементов.