Сортировка

Begin

End

Then

Begin

Begin

Begin

Var

Type

vector = ARRAY [1..N] of integer;

a:vector;

K,i: integer; {К – текущая длина массива}

Max:integer;

F:Boolean;

{здесь функция ввода VVOD}

{здесь функция вывода VIVOD}

function prov(a:integer):Boolean;

prov:=false;

while a>0 do

if a mod 10 = 3 then begin prov:=true; a:=0; end;

a:=a div 10;

end;

end;

{--здесь ввод массива, К – текущая длина--}

f:=true;

for i:=1 to k do {для каждого элемента массива}

if prov(a[i]) {элемент содержит цифру 3}

then iff {это первый, удовлетворяющий условию?}

begin{первый, тогда считаем его исходным значением max}

max:=a[i]; imax:=I;f:=false

else ifa[i]>max {не первый, тогда сравниваем его с max}

then begin max:=a[i]; imax:=I end;

vivod(a,k);{вывод массива для визуальной проверки правильности работы}

writeln(‘Максимум =’,max:6:2)

writeln(‘Его порядковый номер - ‘,imax);

end.

Примечание. Другая модификация алгоритма поиска максимума используется, когда можно выявить закономерность расположения элементов, удовлетворяющих условию, то дополнительную проверку и переменную-флажок можно не использовать, а организовать перебор только тех элементов, номера которых соответствуют условию. Например, если нужны элементы, имеющие четные порядковые номера, то нужно перебирать 2,4,6 и т.д. элементы. Это можно сделать, изменяя индекс массива «вручную» и использовав вместо цикла For цикл While:

I:=2;

While i<=k do

{--здесь обработка элемента--}

I;=i+2;

End;

Сортировка – это процесс упорядочения заданного множества объектов по определенному признаку, например по возрастанию значений элементов или убыванию.

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

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

§ по неубыванию - каждый следующий элемент больше или равен предыдущему,

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

§ по невозрастанию - каждый следующий элемент меньше или равен предыдущему.

Все методы сортировки можно разделить на две группы: прямые и улучшенные. Прямые методы разделяются на три подгруппы:

1. сортировка обменом (например, «пузырьковая» сортировка);

2. сортировка выбором (или выделением);

3. сортировка вставкой (или включением).

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

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

Принцип метода.Массив просматривается слева направо (циклом for) и поочередно сравниваются два соседних элемента. Если их взаимное расположение не удовлетворяет условию упорядоченности (например, первый из пары должен быть меньше второго – это по возрастанию), то они меняются местами. Каждый элемент массива сначала второй в паре, а затем, в следующей паре – первый. Для сортировки по возрастанию в какой-то момент встречается самый большой элемент массива. Когда он оказывается первым в очередной паре, то нарушает условие упорядоченности и меняется местами со вторым. Для следующей пары он становится первым и тоже нарушает упорядоченность. Он снова меняется и т.д.

В итоге после такого прохода на последнее N-е место становится самый большой элемент массива. Он как бы «всплыл» из середины массива в его конец, как пузырек всплывает из глубины на поверхность при кипении воды. Отсюда название метода.

Далее выполняется новый проход, только для элементов от 1 до N-1 позиции, т.к. последний уже на своем месте. «Всплывает» на N-1 позицию следующий после максимума по значению элемент. И так далее. Всего требуется N-1 проход.

Для повторения проходов также используется цикл: либо for, либо while или repeat. Если это цикл For, то количество операций сравнения всегда одинаково, т.к. оба цикла повторяются указанное количество раз вне зависимости от того, отсортирован массив или нет. Это означает, что всегда выполняется ½(n²-n) сравнений, где n – количество элементов в массиве (внешний цикл выполняется n-1 раз, внутренний n/2 раз). Количество перестановок в лучшем случае =0, в среднем ¾(n²-n), в худшем – 3/2(n²-n) раз. Поэтому пузырьковая сортировка называется n-квадратичным алгоритмом, т.к. время его выполнения пропорционально квадрату количества элементов массива.

Рассмотрим работу алгоритма. Пусть N=6 – длина массива, K – длина неотсортированной части массива, которая постепенно уменьшается.

							(N=6)								(N=6)
Проход 1								Проход 2
		9								7				K=
			7			K	=N=6				1
				1								3
					3
Рез-т								Рез-т

(N=6)

(N=6)

Проход 3

Проход 4

1

K=

1

K=

3

3

Рез-т

Рез-т

Проход 5

К=

Рез-т

For p:=1 to n-1 do

For i:=1 to n-1 do

if a[i]>a[i+1] then

Дата добавления: 2014-03-11; просмотров: 352; Нарушение авторских прав

Мы поможем в написании ваших работ!