Реферат: Урок 6 (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;