МЕТОДИЧЕСКАЯ РАЗРАБОТКА УРОКА ДЛЯ 10 КЛАССА «СОРТИРОВКА МАССИВОВ В СРЕДЕ DELPHI-LAZARUS» ШУНТОВА ЛЮДМИЛА ВЛАДИМИРОВНА учитель информатики МОУ Лесногородской сош Одинцовского района Московской области 2011 год

Существует традиционное деление алгоритмов на численные и нечисленные. АЛГОРИТМЫ ЧИСЛЕННЫЕ НЕЧИСЛЕННЫЕ

ЧИСЛЕННЫЕ АЛГОРИТМЫ Математические расчеты (вычисления по формулам, решение уравнений, статистическая обработка и т.д. ДАННЫЕ -ЧИСЛА

АЛГОРИТМЫ НЕЧИСЛЕННЫЕ АЛГОРИТМЫ Системное программирование (трансляторы, ОС),СС управления Б.Д., сетевое программное обеспечение и т.д. ДАННЫЕ- символьная,графическая, мультимедийная информация

Для программных продуктов второй категории наиболее часто используемыми являются алгоритмы сортировки данных. От эффективности их выполнения во многом зависит эффективность работы всей программы. Различают алгоритмы внутренней сортировки – во внутренней памяти внешней сортировки- сортировки файлов

Внешняя (сортировка файлов) Внутренняя (во внутренней памяти) СОРТИРОВКА

Речь пойдет только о внутренней сортировке Как правило, сортируемые данные располагаются в массивах. В простейшем случае – сортируются числовые массивы.

Сортировка- упорядочивание данных по некоторому признаку. (И.Г.Семакин) Сортировка-процесс размещения заданного множества объектов в определенном порядке (убывания или возрастания) (Д.Златопольский) Сортировка- один из наиболее распространенных процессов современной обработки информации. Это распределение элементов множества по группам в соответствии с определенными правилами. (Е.В.Андреева)

Методы сортировки ПРОСТЫЕ СЛОЖНЫЕ Подсчетом Вставками Выбором Обменом Метод Шелла С разделениями Слияниями Пирамидальная

СОРТИРОВКА ПОДСЧЕТОМ Место каждого элемента в отсортированном массиве зависит от количества элементов, меньших его. Например, если значение некоторого элемента исходного массива превышает значения четырех других, то его место в упорядоченной последовательности- пятое. Следовательно, для сортировки надо для каждого элемента массива подсчитать к-во эл-тов, меньших его, и затем разместить каждый рассмотренный элемент на соответствующем месте в новом, специально созданном, массиве.

Исходный массив Упорядоченный массив 1 место (0 элем) 2 место (1 элем) 3 место (2 элем) 4 место (3 элем) 5 место (4 элем) 6 место (5 элем) 7 место (6 элем) 8 место (7 элем)

алг.Сортировка подсчетом {подсчитываем значение k [i] для каждого элемента массива a} нц для I от 1 до n k [i]:=0 кц нц для I от 2 до n нц для j от 1 до i-1 если a [i]

СОРТИРОВКА ВЫБОРОМ Сначала в неупорядоченном массиве выбирается минимальный элемент. Этот элемент исключается из дальнейшей обработки, а оставшаяся последовательность элементов принимается за исходную, и процесс повторяется до тех пор, пока все элементы не будут выбраны. Выбранный в исходном массиве минимальный элемент размещается на первом месте в новом массиве. Однако если на втором просмотре исходного массива вновь найти минимальный элемент, то им окажется тот же самый элемент. Чтобы исключить эту ситуацию, в исходном массиве вместо выбранного, записать число, заведомо превосходя- щее любой элемент исх.массива

алг.Сортировка выбором {Находим минимальный элемент массива и его индекс} min:=a[1] indmin:= 1 нц для j от 2 до n если a [j] < a [indmin] то {увеличиваем значение к для j-го элемента} min:= a [j] indmin := j все кц {записываем минимальный элемент на i-е место в массиве b } b [i] := min {заменяем минимальный элемент исходного массива «большим числом» b [i] := max Кц {выводим на экран отсортированный массив b} нц для I от 1 до n вывод b [i] кц кон

Второй способ сортировки выбором Рассмотренный вариант сортировки обладает двумя недостатками: 1.Требование дополнительного массива 2.Для нахождения минимального элемента и его индек- са на каждом проходе приходится просматривать все элементы массива Указанные недостатки устраняются, если все изменения проводить в исходном массиве: 1.Найти минимальный элемент среди всех элементов массива и поменять его местами с первым элементом 2.Найти минимальный элемент среди второго, третьего и т.д. элементов массива и поменять его местами со вторым элементом и т.д. 3.…. В данной разработке урока применяется именно этот способ

алг.Сортировка выбором for i := 1 to Dreal - 1 do {i - позиция, в которую нужно записать} begin Min1 := ; {нач. значение для поиска минимальный элемента } for j := i to Dreal do {Поиск минимального элемента } begin if Mass [j] < Min1 then {в оставшейся части массива } begin k := j; Min1 := Mass [j]; {к - номер найденного элемента } end; {Min1 - найденное значение } end; { } rab := Mass[i]; {Обмен элементов массива } Mass [i] := Min1; {с номерами (i) и (k) } Mass [k] := rab; { } sss := ''; {Вывод } for rab := 1 to dreal do {текущего } begin sss := sss + intToStr(Mass[rab]) + ' '; {состояния } end; {массива } ListBox3.Items.Add(sss); {в список } ListBox3.ItemIndex := ListBox3.Count - 1; {ListBox3 } sleep(5000); {Задержка } end; ListBox3.Items.Add('OK !'); {Вывод "OK"} end;

СОРТИРОВКА ОБМЕНОМ Метод «пузырька» Метод, при котором все соседние элементы массива попарно сравниваются друг с другом и меняются местами, если предшествующий элемент больше последующего. В результате максимальный элемент постепенно смещается вправо и в конце концов занимает свое место (которое он должен занимать в упорядоченном массиве –крайнее правое), после чего этот элемент исключается из дальнейшей обработки. Затем процесс повторяется, и свое место занимает второй по величине элемент. Так продолжается до тех пор, пока весь массив не будет упорядочен.

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

алг.Сортировка обменом. Метод «Пузырька» begin k := 0; for i := 1 to n-1 do{кол-во повторений} begin for j := 1 to n-1 do begin if Mass [j] > Mass [j + 1] then {Если 2 соседа нарушают } begin rab := Mass[j]; {порядок возрастания, то } Mass[j] := Mass[j + 1]; {производится их обмен } Mass[j + 1] := rab; { } k := k + 1; {к - счетчик обменов } end; { } end; sss := ''; {Вывод } for rab := 1 to Dreal do {текущего } begin sss := sss + intToStr(Mass[rab]) + ' '; {состояния } end; {массива } ListBox3.Items.Add(sss); {в список } ListBox3.ItemIndex := ListBox3.Count - 1; {ListBox3 } sleep(5000); {Задержка } end; ListBox3.Items.Add('OK ! Перестановок= ' + intToStr(k)); {Вывод "OK"} end;

СОРТИРОВКА ВСТАВКАМИ При сортировке вставками(включениями) из неупорядочен- ной последовательности элементов поочередно выбирается каждый элемент, сравнивается с предыдущим (уже упорядоченным) списком и помещается на соответствующее место в нем. В данном примере жирным выделен очередной элемент, а стрелкой- место для его размещения. На второй строке –вид массива после очередного перемещения. 1-й этап: й этап: й этап:

4-й этап: й этап: й этап: й этап:

алг.Сортировка вставками(включениями) ListBox3.Items.Add(intToStr(Mass[1])); {Вывод 1-го массив состоит из 1 элемента} ListBox3.ItemIndex := ListBox3.Count - 1; {вывод текущего массива } sleep(5000); {Задержка } for i := 2 to Dreal do Begin {i - номер элемента, который } for j := 1 to i - 1 do {вставляется в растущий массив } begin if Mass [j] > Mass [i] then {Поиск номера элемента, } begin rab := Mass [i]; {который больше вставляемого } for k := i - 1 downto j do {Если такой элемент найден, } begin {то на его место вставляем } Mass[k + 1] := Mass[k]; {i-й элемент, а остальные } end; {сдвигаем на 1 позицию вправо } Mass[j] := rab; goto Lab1 { } end; { } end; Lab1: sss := ''; {Вывод } for rab := 1 to i do {текущего } begin sss := sss + intToStr(Mass[rab]) + ' '; {состояния } end; {массива } ListBox3.Items.Add(sss); {в список } ListBox3.ItemIndex := ListBox3.Count - 1; {ListBox3 } sleep(5000); {Задержка } end; ListBox3.Items.Add('OK !'); end;

«Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею! Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования.» Д.Кнут

ЛИТЕРАТУРА: 1.Е.В.Андреева Л.Л.Босова И.Н.Фалина «Математические основы информатики» 2. Д.М.Златопольский «Программирование: типовые задачи, алгоритмы, методы» 3. И.Г.Семакин «Информатика» учебник для 10 класса профильный курс 4. И.Г.Семакин А.П.Шестаков «Основы программирования»

СПАСИБО ЗА ВНИМАНИЕ!