Комбинированный урок по теме "Сортировка массивов в среде Delphi-Lazarus"

(см. Презентацию (Приложение)

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

Что такое одномерный массив (определение)?

Приведите пример массивов. Как элементы массива обозначаются? Как массив объявляется в программах Т.Паскаль?

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

Актуализация знаний:

Задача (№23) из задачника- практикума И.Г.Семакина:

Последовательность а1,а2,..аn состоит из нулей и единиц.

Поставить в начало этой последовательности нули, а в конце массива – единицы.

Вопрос: Какие возможны варианты? С чего надо начать решение?

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

2. Затем- внутренний цикл (сравнивать поочередно данный элемент со всеми другими элементами)

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

Примеры числовых массивов: оценки, цены на товары, номера домов на улице, температуры за определенный период времени и т.д.

Примеры объявления массивов:

Type
Mas1=Array [1..100] of integer;
Mas2=Array [-10..10] of char;

Var Num: Mas1; Sim: Mas2;

2. Решают задачу №23 из задачника- практикума И.Г.Семакина по теме “Линейные массивы”.

Один из возможных вариантов программы:

const n=5;
var a: array[1..n] of integer;
r,k,i:integer;
begin
for i:=1 to n do
begin
{ввод массива}
write (‘введите a[‘,i,’] );
readln (a[i]);
end;
for i:=1 to n-1 do {цикл по каждому элементу}
begin
for k:=1 to n-i do {сравнение с каждым элементом }
begin
if a[k]> a[k+1] then
begin
r:= a[k]; a[k]:= a[k+1]; a[k+1]:=r;
end;
end;
end;
end.

Тема сегодняшнего урока: “Сортировка массивов”

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

При решении предыдущей задачи вы столкнулись с задачей примитивной сортировки: выделение нулей из массива и заполнение ими начала массива.

Таким образом, единицы попадают в конец массива.

Это частный случай сортировки.

В данной презентации рассмотрены более сложные случаи сортировки массивов из самых разнообразных чисел.

(Показ Приложения)

Опорные слайды презентации:

слайд 8

Сортировка – упорядочивание данных по некоторому признаку.
(И.Г.Семакин)[1]

Сортировка – процесс размещения заданного множества объектов в определенном порядке (убывания или возрастания)
(Д.М. Златопольский)[2]

Сортировка – один из наиболее распространенных процессов современной обработки информации. Это распределение элементов множества по группам в соответствии с определенными правилами.
(Е.В.Андреева)[3]

слайд 9

слайд 10

СОРТИРОВКА ПОДСЧЕТОМ [2]

Место каждого элемента в отсортированном массиве зависит от количества элементов, меньших его.

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

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

слайд 13

СОРТИРОВКА ВЫБОРОМ [2]

Сначала в неупорядоченном массиве выбирается минимальный элемент.

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

Однако, если на втором просмотре исходного массива вновь найти минимальный элемент, то им окажется тот же самый элемент.

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

слайд 17

СОРТИРОВКА ОБМЕНОМ [2]

Метод “пузырька”

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

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

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

слайд 21

СОРТИРОВКА ВСТАВКАМИ [2]

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

В данном примере жирным выделен очередной элемент, а стрелкой – место для его размещения. На второй строке – вид массива после очередного перемещения.

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

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

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

слайд 22

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

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

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

слайд 24 – ссылка на демонстрационный файл.

Теперь вы знаете, что существуют различные методы сортировки массивов.

Они делятся на простые и сложные.

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

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

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

сортировка подсчетом – это (см.выше)
сортировка вставками – это (см.выше)
сортировка выбором – это (см.выше)
сортировка обменами – это (см.выше)

Данный урок занимает важное место при изучении такой темы как “линейные массивы”.

И завершить сегодняшний урок хочу следующим интересным и точным высказыванием по теме сортировки массивов Д.Кнута:

“Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею!

Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования”.