Урок 6 (1 час) Тема урока

Вид материала

Содержание

Предварительные замечания.
Var IOR : Word; Begin
Пример 5 13 7 9 1 8 16 4 10 2 Сортировка выбором
Var X: T_Mas); Var
Сортировка обменом (метод "пузырька")
1. Сортировка методом прямого включения
A := x[k]; j := k-1
1. Сортировка с разделением ("быстрая" сортировка, метод Хоара)

Подобный материал:

Давыдова Е.В., школа № 444

Урок 6 (1 час)

Тема урока. Сортировка массивов

Цель урока. Познакомить учащихся с основными алгоритмами сортировки одномерных массивов.

План урока.

1. Общие замечания.

2. Сортировка методом выбора.

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

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

Зачем нужна сортировка?

Легче работать с отсортированными данными, чем с произвольно расположенными данными:

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

Предварительные замечания.

Общий вид программы сортировки:

Uses Crt;

Const N = 50;

Type T_Mas = Array [1..N] of Integer;

Var Mas : T_Mas;

Kol : Integer;

Procedure Count (Var Kol_1:Integer);

{Процедура определения размерности массива}

Var IOR : Word;

Begin

Write('Введите размерность массива: ');

Repeat

{$I-} ReadLn(Kol_1); {$I+}

IOR := IOResult;

If (IOR <> 0) or (Kol_1>N) Then

WriteLn('Ошибка. Повторите ввод.')

Until (Kol_1<=N) and (IOR=0)

End;

Procedure Filling (Kol_1:Integer; Var A: T_Mas);

{Процедура заполнения массива}

Var I : Integer;

Begin

Randomize;

For I := 1 To Kol_1 Do A[I] := Random(N)

End;

Procedure Print (Kol_1:Integer; A: T_Mas);

{Процедура вывода массива}

Var I : Integer;

Begin

For I:=1 to Kol_1 do Write (A[I], ' ')

End;

Procedure Sort_Metod_ (Kol_1:Integer; Var X: T_Mas);

{Процедура сортировки по методу . . .}

Begin

ClrScr;

Count(Kol);

Filling(Kol, Mas);

WriteLn('Исходный массив'); Print (Kol, Mas);

Sort_Metod_ (Kol, Mas);

WriteLn;

WriteLn('Отсортированный массив'); Print (Kol, Mas);

Repeat until KeyPressed

End.

Пример

5 13 7 9 1 8 16 4 10 2

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

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

Блок-схема

Нет

Нет

Нет

Программа

Procedure Sort_Metod_Choice (Kol_1:Integer; Var X: T_Mas);

Var K, J, Min, I_Min : Integer;

Begin

For K:=1 to Kol_1 do

begin

Min := X [K]; I_Min := K;

For J := K+1 to Kol_1 do

If X[J] < Min Then

begin Min:= X[J]; I_Min:=J end;

X[I_Min] := X[K]; X[K] :=Min

end

End;

Задание

Подсчитать количество произведенных сравнений.
Подсчитать количество произведенных перестановок.
Изменить процедуру сортировки так, чтобы сортировка начиналась с последнего элемента массива (с конца, индекс К - уменьшался).
Отсортировать четные элементы массива.

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

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

Блок-схема.

Нет

Нет

Да

Программа

Procedure Sort_Metod_Bubble (Kol_1:Integer; Var X: T_Mas);

Var K, A : Integer;

Flag : Boolean;

Begin

Repeat

Flag := False;

For K := 2 to Kol_1 do

If X[K] < X [K-1] Then

begin

A := X[K-1];

X[K-1] := X[K];

X[K] := A;

Flag:= True

end;

Kol_1 := Kol_1 – 1;

Until not Flag

End;

Задание

Подсчитать количество произведенных сравнений.
Подсчитать количество произведенных перестановок.
Сравнить сортировку методами выбора и обмена по количеству сравнений и перестановок.
Описать процедуру "пузырьковой" сортировки по убыванию.

Урок 7 (1 час)

Тема урока. Сортировка массивов (продолжение).

Цель урока. Познакомить учащихся с основными алгоритмами сортировки одномерных массивов.

План урока.

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

2. Слияние двух массивов.

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

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

место вставки очередной элемент

1 этап	38	12	80	15	36	23	74	62

2 этап	12	38	80	15	36	23	74	62

3 этап	12	38	80	15	36	23	74	62

4 этап	12	15	38	80	36	23	74	62

5 этап	12	15	36	38	80	23	74	62

6 этап	12	15	23	36	38	80	74	62

7 этап	12	15	23	36	38	74	80	62

	12	15	23	36	38	62	74	80

Procedure Sort_Metod_Insert (Kol_1:Integer; Var X: T_Mas);

Var K, J, A : Integer;

Begin

For K := 2 to Kol_1 do

begin

A := X[K]; J := K-1;

While (J > 0) and (A <= X[J]) do

begin X[J+1] := X[J]; Dec(J) end;

X[J+1] := A

end

End;

2. Слияние двух массивов

Дан массив X[1..N] и числа K, M, N, такие, что K<=M<=N. Описать процедуру, которая сливает отрезки массива, X[K+1], . . , X[M] и X[М+1], . . , X[N] в упорядоченный отрезок массива X[K+1], . . , X[N].

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

Procedure Sort_Metod_Merge (K, M, N:Integer; Var X: T_Mas);

Var I, J, L : Integer;

C : T_Mas;

Begin

I := K+1; J := M+1; L := 1;

While (I <=M) and (J <=N) Do {Пока не закончится хотя бы одна часть}

begin

If X[I] <= X[J] Then

begin C[L] := X[I]; Inc(I) end

Else

begin C[L] := X[J]; Inc(J) end;

Inc(L)

end; {Один из массивов обработан полностью}

{Перенос в С остатка другого массива-части}

While I <= M Do

begin C[L] := X[I]; Inc(I); Inc(L) end;

While J <= N Do

begin C[L] := X[J]; Inc(J); Inc(L) end;

{Перенос из вспомогательного массива С в массив Х}

For I := 1 to L do X[K+I] := C[I]

End;

Задание

1. Написать программу, в которой массив разбивается на три части. Вторая и третья часть массива отдельно сортируются, а затем объединяются с помощью алгоритма слияния.

2. Написать программу, которая сортирует один массив 3-мя способами и сравнивает их по времени сортировки. Количество элементов массива не менее 500.

Урок 8 (1 час)

Тема урока. Сортировка массивов (продолжение).

Цель урока. Познакомить учащихся с основными алгоритмами сортировки одномерных массивов.

План урока.

1. Сортировка с разделением ("быстрая" сортировка, метод Хоара).

2. Рекурсия.

1. Сортировка с разделением ("быстрая" сортировка, метод Хоара)

1. В исходном не отсортированном массиве выбрать некоторый элемент x=a[k] (барьерный элемент).

2. Переставить элементы массива таким образом, чтобы слева от х оказались элементы массива, меньше или равные х, а справа – элементы массива, больше х.

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

Сначала имеем i = 1, j = n (в рассматриваемом случае число элементов массива n=16). Значение основного элемента обозначим m.

Сравним m и a[j]. Если a[j]>m, то устанавливаем j=j-1 и проводим следующее сравнение m и a[j]. Продолжаем уменьшение j до тех пор, пока не достигнем a[j]<=m. Тогда поменяем местами элементы a[j] и a[i] (строку 5, обмен значений 38 и 4) , установим значение i = i+1 и, сравнивая элементы a[i] со значением m. После следующего обмена (строка 10, элементы со значениями 79 и 38) опять уменьшим j, и будем просматривать элементы справа налево и т.д. до тех пор, пока не станет j<=i.

i															j
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	Действия
38	8	16	6	79	76	57	24	56	2	58	48	4	70	45	47	исходный массив
38															47	уменьшение j
38														45		-
38													70			-
38												4				4 < 38
4												38				обмен
	8											38				увеличение i
		16										38				-
			6									38				-
				79								38				79 > 38
				38								79				обмен
				38							48					уменьшение j
				38						58						-
				38					2							2 < 38
				2					38							обмен
					76				38							увеличение i
					38				76							обмен
					38			56								уменьшение j
					38		24									24 < 38
					24		38									обмен
						57	38									увеличение i
						38	57									обмен
4	8	16	6	2	24	38	57	56	76	58	48	79	70	45	47	полученный массив

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

Программа

Вспомогательная процедура, выполняющая разделение массива с границами L и R на две части.

Procedure Partition (L,R : Integer; Var A : T_Mas);

Var I, J, M, Tmp : Integer;

Begin

If L < R {условие продолжения рекурсии} Then

begin

I := L; J := R;

M := A[I];

Repeat

While M < A[J] Do {Уменьшение указателя J}

J := J -1;

If I <= J Then

begin {Обмен}

Tmp:= A[I]; A[I] := A[J]; A[J] := Tmp;

I := I + 1;

end;

While M > A[I] Do {Увеличение указателя I}

I := I + 1;

If I <= J Then

begin {Обмен}

Tmp:= A[I]; A[I] := A[J]; A[J] := Tmp;

J := J - 1;

end;

until I > J;

Partition (L, J, A); {Разделяем левую часть}

Partition (I, R, A); {Разделяем правую часть}

end

end;

Procedure Sort_Metod_Quick (Kol_1:Integer; Var X: T_Mas);

Begin

Partition (1, Kol_1, X)

End;

Blog

Урок 6 (1 час) Тема урока

Содержание

Предварительные замечания.

Пример

5 13 7 9 1 8 16 4 10 2

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

Блок-схема

Задание

Задание

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