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

Обменная сортировака с разделением (сортировка Хоара)

Сортировка методом слияний

Сортировка методом прямого включения

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

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

Методы сортировки и поиска информации

Лекция 9

1. Сортировака

2. Алгоритмы поиска информации

2.1. Линейный поиск

2.2. Линейный поиск с использованием барьера

2.3. Бинарный поиск

3. Поиск подстроки в строке

3.1. Прямой поиск

3.2. Алгоритм Р. Бойера и Дж. Мура

4. Пример

Для решения многих задач удобно сначала упорядочить данные по определенному признаку. Процесс упорядочивания заданного множества объектов по заданному признаку называется сортировкой.

Данные, например, элементы массива, можно отсортировать:

· по возрастанию – каждый следующий элемент больше предыдущего:

a[1] < a[2] <... < a[n];

· по неубыванию – каждый следующий элемент не меньше предыдущего:

a[1] ≤ a[2] ≤... ≤ a[n];

· по убыванию – каждый следующий элемент меньше предыдущего:

a[1] > a[2] >... >a[n];

· по невозрастанию – каждый следующий элемент не больше предыдущего: a[1] ≥ a[2] ≥... ≥ a[n].

Простейшими примерами могут служить следующие задачи.

Сортировка

Этот метод сортировки обычно применяется для массивов, не содержащих повторяющихся элементов. Для достижения поставленной цели можно действовать следующим образом:

1. выбрать максимальный элемент массива;

2. поменять его местами с последним элементом (после этого наибольший элемент будет стоять на своем месте);

3. повторить пп.1-2 с оставшимися n-1 элементами, то есть рассмотреть часть массива, начиная с первого элемента до предпоследнего, найти в ней максимальный элемент и поменять его местами с предпоследним (n-1) - м элементом массива и так далее, пока не останется один элемент, уже стоящий на своем месте.

Всего потребуется n-1 раз выполнить эту последовательность действий. В процессе сортировки будет увеличиваться отсортированная часть массива, а не отсортированная, соответственно, уменьшаться.

Рассмотрим этот процесс на примере. Пусть исходный массив а состоит из 10 элементов и имеет вид:

5 13 7 9 1 8 16 4 10 2

После сортировки массив должен выглядеть так:

1 2 4 5 7 8 9 10 13 16

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

1-й шаг: рассмотрим весь массив и найдем в нем максимальный элемент -16 (он стоит на седьмом месте); поменяем его местами с последним элементом.

5 13 7 9 1 8 16 4 10 2

Максимальный элемент помещен на свое место.

2-й шаг: рассмотрим часть массива с первого до девятого элемента. Максимальный элемент этой части стоит на втором месте и имеет значение 13. Поменяем его местами с последним элементом этой части.

5 13 7 9 1 8 2 4 10 16

Отсортированная часть массива состоит теперь уже из двух элементов.

3-й шаг: снова уменьшим рассматриваемую часть массива на один элемент. Здесь нужно поменять местами второй элемент (его значение 10) и последний элемент этой части (его значение 4).

5 10 7 9 1 8 2 4 13 16

В отсортированной части массива теперь стало 3 элемента.

4-й шаг: аналогично.

5 4 7 9 1 8 2 10 13 16

5-й шаг: максимальный элемент этой части массива является последним в ней, поэтому его нужно оставить на своем месте.

5 4 7 2 1 8 9 10 13 16

Далее действуем аналогично.

6-й шаг:

5 4 7 2 1 8 9 10 13 16

7-й шаг:

5 4 1 2 7 8 9 10 13 16

8-й шаг:

2 4 1 5 7 8 9 10 13 16

9-й шаг:

2 1 4 5 7 8 9 10 13 16

Итог: 1 2 4 5 7 8 9 10 13 16

Для программной реализации этого процесса необходимо организовать цикл по длине рассматриваемой части массива, которая изменяется от n до 2. В качестве начального значения максимума разумно взять значение последнего элемента рассматриваемой части.

Теперь можем записать алгоритм сортировки:

For i: = n Downto 2 Do

Begin

найти максимальный элемент из a[1],..., a[i]; запомнить его индекс в переменной

k; если i<>k поменять местами a[i] и a[k]

End;

Опишем этот алгоритм подробно:

program n1;

type ar=array [1..10] of integer;

var i:integer;

a:ar;

Procedure sorting1(var a:ar);

{поскольку в процессе работы процедуры массив изменится, формальный

параметр а описывается как параметр-переменная}

var i,j,k:integer;

m:integer;

{значение максимального элемента рассматриваемой части массива}

begin

for i:=10 downto 2 do

{цикл по длине рассматриваемой части массива}

begin

{поиск максимального элемента и его номера в текущей части массива}

k:=i;

m:=a[i];

{начальные значения максимального элемента и

его индекса в рассматриваемой части массива}

for j:=2 to i-1 do

if a[j]>m then begin k:=j; m:=a[k] end;

if k<>i then

begin {перестановка элементов}

a[k]:=a[i];

a[i]:=m;

end;

end;

end;

begin

writeln('Введите исходный массив:');

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

sorting1(a);

writeln('Отсортированный массив:');

for i:=1 to 10 do write(a[i],' ');

writeln;

end.

При решении практических задач упорядочивание x1,...xn как правило сопровождается некоторыми дополнительными действиями. Например, если x1, y1, x2, y2,..., xn, yn - это значения аргумента x и некоторой функций y=f(x), то перестановка x1,..., xn должна сопровождаться перестановкой y1,..., yn. Элементы y1,..., yn переставляются так же, как x1,..., xn вне зависимости от значений самих

y1,..., yn. Рассмотрим эту задачу; переставленные значения x1, y1, x2, y2,..., xn будут выведены в два столбца:

x1 y1

x2 y2

.....

xn yn

program tab;

const n=5;

type u=array[1..n] of real;

var x,y:u;

v:real;

i,j,k:integer;

begin

for i:=1 to n do read(x[i],y[i]);

for i:=1 to n do begin

k:=i;

for j:=i+1 to n do

if x[j]<x[k] then k:=j;

v:=x[i]; x[i]:=x[k]; x[k]:=v;

v:=y[i]; y[i]:=y[k]; y[k]:=v;

writeln(x[i],y[i]);

end;

end.

Дата добавления: 2014-11-09