Delphi_part2

8 ЛАБОРАТОРНАЯ РАБОТА № 8. СОРТИРОВКА МАССИВОВ

Цели работы:

–Познакомиться с понятием сортировки массивов.

–Познакомиться с сортировкой массива посредством выбора.

–Познакомиться с сортировкой обменом (метод пузырька).

–Познакомиться с сортировкой массива методом вставки.

–Познакомиться с операцией – вставка элемента в отсортированный массив.

–Создать приложение, в котором наглядно выполняется сортировка одномерного массива различными методами, а также вставка элемента в отсортированный массив. Обеспечить выбор операции над массивом с помощью компонента MainMenu. Используя знакомые уже компоненты Memo или Edit осуществить возможность обмена данными между массивом и экраном.

8.1 МЕТОДЫ СОРТИРОВКИ МАССИВОВ

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

Сортировка массива – процесс перестановки элементов массива с целью размещения элементов массива в определенном порядке.

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

A[1] < A[2] < A[3] < …….< A[n]

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

Существуют различные методы сортировки массивов. Самыми простыми методами сортировки являются:

–сортировка выбором;

–сортировка обменом (метод пузырька);

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

21

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

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

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

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

3.Просматривается массив от второго элемента, находится минимальный среди оставшихся и помещается на место второго элемента.

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

1 sortChoise(mas,count)

Номер изменяемого

2

i := 1

элемента

3

i <= count-1

10

нет

да

4

Номер элемента, который

j := i + 1

сравненивается с изменяемым

5

j <= count

9

нет

нет

да

6

mas[j] < mas[i]

7

tmp := mas[i]

Меняем местами изменяемый

mas[i] := mas[j]

элемент и сравниваемый

mas[j] := tmp

8

j := j + 1

9

i := i + 1

5

конец

10

3

Рисунок 8.1 - Алгоритм сортировки по возрастанию методом выбора

Анализ описанных выше действий при сортировке выбором показывает, что для программной реализации этого метода сортировки потребуется два цикла for.

Во внешнем цикле должен изменяться номер изменяемого элемента от первого до предпоследнего. Этот цикл будет определять количество проходов

22

по массиву.

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

В теле внутреннего цикла производится сравнение элементов, индексы которых задаются параметрами внешнего и внутреннего цикла. Если при сравнении оказывается, что порядок следования элементов нарушен, то сравниваемые элементы меняются местами.

Схема алгоритма сортировки массива методом выбора показана на рисунке 8.1.

Исходными данными для алгоритма являются: сортируемый массив mas и количество элементов в этом массиве count.

8.1.1.1 Пример сортировки массива по возрастанию методом выбора

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

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

Если значение текущего элемента						оказывается меньше значения изменяемого,
то значения этих элементов массива меняются местами.
		Когда	будут просмотрены			все	текущие элементы,		то значение
изменяемого элемента окажется меньшим из всех текущих.
		Проиллюстрируем алгоритм этой сортировки рисунками. Исходное
расположение элементов массива показано на рисунке 8.2.
		A[1]		A[2]		A[3]		A[4]	A[5]
		10		5		6		2	7

5<10 - необходимо поменять местами A[1] и A[2]

Рисунок 8.2 – Исходная схема сортируемого массива

После обмена местами A[1] и A[2] массив будет иметь вид, показанный на рисунке 8.3.

A[1]	A[2]	A[3]	A[4]	A[5]
5	10	6	2	7

5 < 6, поэтому элементы A[1] и A[3] не нужно менять местами

Рисунок 8.3 – Схема сортируемого массива после первого обмена элементов

Далее будут сравниваться элементы A[3] и A[1], но так как A[3]не меньше A[1] , то A[3] остается на месте.

23

Анализ элемента A[4] показывает, что он меньше, чем A[1], поэтому его следует поменять местами с A[1]. Результат изменений показан на рисунке 8.4.

	A[1]		A[2]	A[3]		A[4]			A[5]
	5		10	6		2			7
							A[1] и A[4]
		5>2 - необходимо менять местами
	После обмена массив будет иметь вид:
	A[1]		A[2]	A[3]		A[4]			A[5]
	2		10	6		5			7

Рисунок 8.4 – Схема сортируемого массива после второго обмена элементов

Далее будут сравниваться элементы A[5] и A[1], но так как A[5]не меньше A[1] , то A[5] остается на месте.

На этом первый проход сортируемого массива заканчивается. В результате этого прохода в первой позиции массива оказался наименьший элемент.

Теперь необходимо осуществить второй проход по массиву, но в качестве изменяемого берется уже второй элемент массива. Со вторым элементом будут сравниваться элементы, начиная с третьего. В результате чего на второе место будет поставлен минимальный элемент среди элементов со 2-го по 5-й. Результаты второго прохода по массиву представлены на рисунке 8.5.

A[1]			A[2]					A[3]			A[4]			A[5]
	2		10					6			5			7
											A[2] и A[3]
							10>6 - нужен обмен
A[1]			A[2]					A[3]			A[4]			A[5]
	2		6					10			5			7
							6>5 - нужен обмен				A[2] и A[4]
A[1]			A[2]					A[3]			A[4]			A[5]
	2				5			10			6			7

5<7 - обмен A[2] и A[5] не нужен

Рисунок 8.5 – Схема второго прохода при сортировке массива методом выбора

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

24

начиная с четвертого. В результате третий и четвертый элементы поменяются местами.

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

	A[1]			A[2]			A[3]				A[4]				A[5]
		2			5		10				6				7
	A[1]			A[2]			A[3]				A[4]				A[5]
		2			5			6			10				7
	A[1]			A[2]			A[3]				A[4]				A[5]
		2			5			6				7			10

Рисунок 8.6 – Схема последних проходов по массиву при сортировке методом выбора

8.1.1.2 Процедура сортировки массива методом выбора

procedure SortChoise (var a: TArray100; count: integer); var i, j, x: integer;

begin

for i := 1 to count - 1 do begin

for j := i + 1 to count do if a[j] > a[i] then begin

x := a[i]; a[i] := a[j]; a[j] := x;

end;

end; end;

25

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

Алгоритм основан на принципе сравнения и обмена пары соседних элементов.

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

1

sortBuble(mas,count)

2

Номер последнего из

last := count

сравниваемых элементов

3

ok := true

Признак порядка в массиве

Номер сравнения при

4

i := 1

очередном проходе

5

i <= last-1

нет

10

нет

да

6

mas[i] > mas[i+1]

да

7

tmp := mas[i]

mas[i] := mas[i+1]

Меняем местами элементы

mas[i+1] := tmp

8

ok := false

9

5

i := i + 1

Номер последнего из

10

сравниваемых элементов после

last := last - 1

каждого прохода уменьшается

нет

11

ok = true ?

да

12

конец

Рисунок 8.7 – Алгоритм сортировки по возрастанию методом обмена

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

Затем все повторяется заново и наибольший среди оставшихся элементов

26

оказывается на предпоследнем месте.

Таким образом, элементы с меньшим значением продвигаются к началу массива (всплывают), а элементы с большим значением – к концу массива (тонут). Этот метод получил название метод пузырька, что, очевидно, если располагать массивы вертикально.

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

Схема алгоритма сортировки массива методом обмена показана на рисунке 8.7.

Сортировка реализуется с помощью двух циклов. Внешний цикл выполняется до тех пор, пока при завершении очередного прохода по массиву не окажется, что перестановок элементов делать не пришлось. В этом случае переменная ok сохранит значение true, и это будет означать, что массив отсортирован. Так как условие отсутствия перестановок элементов при проходе по массиву можно проверить только после завершения прохода, то очевидно, что в данном случае следует использовать цикл repeat ... until.

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

8.1.2.1 Пример сортировки массива по возрастанию методом обмена

На рисунках 8.8 – 8.12 подробно показаны изменения массива в процессе сортировки обменом во время первого прохода по массиву.

A[1]	A[2]	A[3]	A[4]	A[5]
10	5	6	2	7

5<10 - необходимо поменять местами A[1] и A[2]

Рисунок 8.8 – Массив перед сортировкой обменом

27

После обмена местами A[1] и A[2] массив имеет вид:
A[1]	A[2]	A[3]	A[4]	A[5]
5	10	6	2	7
	6<10, A[2] и A[3] необходимо поменять местами.
	Рисунок 8.9 – Массив после первого обмена элементов

После обмена местами A[2] и A[3] массив имеет вид:
A[1]	A[2]	A[3]	A[4]	A[5]
5	6	10	2	7
			2<10
	A[3] и A[4] необходимо поменять местами.
	Рисунок 8.10 – Массив после второго обмена элементов

После обмена местами A[3] и A[4] массив имеет вид:
A[1]	A[2]	A[3]	A[4]	A[5]
5	6	2	10	7
			7<10
	A[4] и A[5] необходимо поменять местами.
	Рисунок 8.11 – Массив после третьего обмена элементов

После обмена местами A[4] и A[5] массив имеет вид:
	A[1]	A[2]	A[3]	A[4]	A[5]
	5	6	2	7		10

Рисунок 8.12 – Массив после первого прохода

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

Второй проход по массиву рассмотрим менее детально. Его результаты представлены на рисунке 8.13.

28

A[1]	A[2]	A[3]	A[4]	A[5]
5	6	2	7	10
	5<6 обмен не нужен
A[1]	A[2]	A[3]	A[4]	A[5]
5	6	2	7	10
	6>2	- обмен A[2] и A[3]
A[1]	A[2]	A[3]	A[4]	A[5]
5	2	6	7	10
			6<7- обмен не нужен
	Рисунок 8.13 – Второй проход по массиву

Во втором проходе понадобился только один обмен, и в результате не только A[4], но и A[3] оказались на своих местах.

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

Результаты последнего прохода по массиву показаны на рисунке 8.14.

Третий проход по массиву:
A[1]	A[2]	A[3]	A[4]	A[5]
5	2	6	7	10
5>2 – нужен обмен A[1] и A[2]
A[1]	A[2]	A[3]	A[4]	A[5]
2	5	6	7	10
		5<6- обмен не нужен, элемент на месте
	Рисунок 8.14 – Результаты третьего проход по массиву
8.1.2.2 Процедура сортировки массива методом обмена

procedure SortBubl(var a: TArray100; count: integer); var last, i, x: integer; ok: boolean;

begin

last := count; repeat

ok := true;

29

for i:= 1 to last - 1 do

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

x := a[i];

a[i] := a[i+1]; a[i+1] := x; ok := false;

end; last := last - 1;

until ok; end;

8.1.3 Сортировка вставкой или включением

Суть алгоритма в следующем – элементы массива разделяют на упорядоченную часть А[1], А[2], ……, А[i-1], которая располагается в начале массива, и остальную, неупорядоченную часть А[i], ……., А[N], а затем, по одному, элементы из неупорядоченной части переносятся в упорядоченную.

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

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

Как видно из рисунка 8.15, в алгоритме есть два цикла.

Во внешнем цикле последовательно изменяется номер левой границы неупорядоченной области от значения i = 2 до i = count. В теле этого цикла производится сравнение элементов, находящихся по обе стороны от границы, разделяющей упорядоченную и неупорядоченную части. Если порядок нарушен, то первый элемент неупорядоченной последовательности запоминается в переменной tmp и, тем самым, освобождается место для сдвигов упорядоченных элементов вправо.

30