Сортировка методом прямого обмена

Сортировка методом прямого выбора

Алгоритм сортировки массива по возрастанию методом прямого выбора может быть представлен так:

1. Просматривая массив от первого элемента, найти минимальный и поместить его на место первого элемента, а первый на место минимального.

2. Просматривая массив от второго элемента, найти минимальный и поместить его на место второго элемента, а второй на место минимального.

3. И так далее до предпоследнего элемента.

Ниже представлена программа сортировки массива целых чисел по возрастанию. Для демонстрации процесса сортировки программа выводит массив после каждого обмена элементов.

Const

SIZE=5;

var

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

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

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

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

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

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

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

к: integer;

begin

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

write( ’Bвeдите ’ ,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]}

min:=i;

for j:= i + l to SIZE do

begin

if a[j] < a[min] then min:=j;

{поменяем местами a[min] и a[i]}

buf := a[j];

a[i] := a[min];

a[min] := buf;

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

for k:=l to SIZE do

write(a[k], ’ ’ );

writeln;

end;

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

end.

Пример работы программы:

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

Введите 5 целых в одной строке через пробел и нажмите <Enter>

12 -3 56 47 10

Сортировка

-3 12 56 47 10

-3 10 56 47 12

-3 10 12 47 56

Массив отсортирован.

Сортировка методом прямого обмена

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

На рисунке 1 показан пример процесса сортировки массива. Буквой ("а") обозначено исходное состояние массива и перестановки на первом проходе, буквой ("б") - состояние после перестановок на первом проходе и перестановки на втором проходе и так далее.

Сортировка методом прямого обмена - student2.ru

Рисунок 1 – Процесс сортировки массива

Ниже представлена программа сортировки массива целых чисел по возрастанию. Для демонстрации процесса сортировки программа выводит массив после каждого цикла обменов.

Const

SIZE = 5;

var

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

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

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

buf: integer;

begin

writeln(Copтиpoвкa массива пузырьковым методом.);

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

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

for k := l to SIZE do

read( a[k] );

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

for i:= l to SIZE-1 do

begin

for k:=l to SIZE-1 do begin

if a[k] > a[ k + l ] then begin

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

buf := a[k];

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

a[k+l]:=buf;

end;

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

writeln;

end;

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

end.

Пример работы программы:

Сортировка массива пузырьковым методом.

Введите 5 целых в одной строке через пробел и нажмите <Enter>

3 2 4 5 1

Сортировка.

2 3 4 1 5

2 3 1 4 5

2 1 3 4 5

1 2 3 4 5

Массив отсортирован.

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

Uses Crt;

Var

a:array[1..10] of byte;

b, i, p : byte;

Begin

ClrScr;

writeln (’Заполнение массива из 10 элементов целыми числами’);

For i :=l to 10 do

a[i]:=random(255);

writeln (’Вывод массива в строку: ’);

For i :=l to 10 do

write(a[i]:7:2);

writeln;

repeat {сортировка массива}

p:=0;

for i := 1 to 9 do

if a[i] < a[i+l] then

begin

b:=a[i];

a[i]:=a[i+l];

a[i+l]:=b;

p:=l;

end;

until p = 0;

Writeln;

Writeln(’Вывод массива после сортировки: ’);

for i:=l to 10 do

Writeln(i, ’-й элемент массива = ’,a[i]);

Readln;

End.

Поиск в массиве

При решении многих задач возникает необходимость установить, содержит ли массив определенную информацию или нет. Например, проверить, есть ли в массиве фамилий студентов фамилия "Петров". Задачи такого типа называются поиском в массиве.

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

Ниже приведен текст программы поиска в массиве целых чисел. Перебор элементов массива осуществляет инструкция REPEAT, в теле которой инструкция IF сравнивает текущий элемент массива с образцом и присваивает переменной naiden значение TRUE, если текущий элемент равен образцу. Цикл завершается, если в массиве обнаружен элемент, равный образцу (naiden=TRUE), или если проверены все элементы массива. По завершении цикла, по значению переменной found можно определить, успешен поиск или нет.

var

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

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

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

i: integer;

begin

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

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

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

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

write(’->’);

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

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

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

readln( obrazec);

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

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

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

repeat

if massiv[i] = obrazec

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

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

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

{ последний элемент массива }

if naiden then writeln(’Cовпадение с элементом номер’, i:3, ’. Поиск успешен. ’)

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

end.

Вот пример работы программы:

Поиск в массиве.

Введите 10 целых в одной строке через пробел и нажмите <Enter>

->123 45 -17 23 56 2 -8 0 14 324

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

Совпадение с элементом номер 6. Поиск успешен.

Очевидно, что чем больше элементов в массиве и чем дальше расположен нужный элемент от начала массива, тем дольше будет программа искать нужный элемент.

Так как операции сравнения применимы как к числам, так и к строкам, то данный алгоритм может использоваться для поиска как в числовых, так и в строковых массивах.

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

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

Суть метода бинарного поиска заключается в следующем. Выбирается средний элемент упорядоченного по возрастанию массива (элемент с номером sred), с которым сравнивается образец (рисунок 2).

Сортировка методом прямого обмена - student2.ru

Рисунок 2 – Выбор среднего элемента массива при бинарном поиске.

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

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

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

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

Ниже представлен текст программы бинарного поиска в массиве. В программу добавлены операторы вывода значений переменных verh, niz и sred.

var

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

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

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

{ элементов массива}

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

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

i: integer;

begin

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

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