Презентация "Сортировка массивов в среде DELPHI - LAZARUS" 10 класс

Подписи к слайдам:
  • МЕТОДИЧЕСКАЯ РАЗРАБОТКА УРОКА
  • ДЛЯ 10 КЛАССА
  • «СОРТИРОВКА МАССИВОВ
  • В СРЕДЕ DELPHI-LAZARUS»
  • ШУНТОВА ЛЮДМИЛА ВЛАДИМИРОВНА
  • учитель информатики
  • МБОУ Лесногородской сош
  • Одинцовского района Московской области
  • 2013 год
  • Существует традиционное деление алгоритмов на численные и нечисленные.
  • АЛГОРИТМЫ
  • ЧИСЛЕННЫЕ
  • НЕЧИСЛЕННЫЕ
  • ЧИСЛЕННЫЕ АЛГОРИТМЫ
  • Математические расчеты
  • (вычисления по формулам,
  • решение уравнений,
  • статистическая обработка и т.д.
  • ДАННЫЕ -ЧИСЛА
  • АЛГОРИТМЫ
  • НЕЧИСЛЕННЫЕ АЛГОРИТМЫ
  • Системное программирование
  • (трансляторы, ОС),СС управления Б.Д.,
  • сетевое программное обеспечение и т.д.
  • ДАННЫЕ-символьная,графическая, мультимедийная информация
  • Для программных продуктов второй категории наиболее часто используемыми являются алгоритмы сортировки данных.
  • От эффективности их выполнения во многом зависит эффективность работы всей программы.
  • Различают алгоритмы
  • внутренней сортировки – во внутренней памяти внешней сортировки- сортировки файлов
  • Внешняя
  • (сортировка файлов)
  • Внутренняя
  • (во внутренней памяти)
  • СОРТИРОВКА
  • Речь пойдет только о внутренней сортировке
  • Как правило, сортируемые данные располагаются в массивах.
  • В простейшем случае – сортируются числовые массивы.
  • Сортировка- упорядочивание данных по некоторому признаку.
  • (И.Г.Семакин)
  • Сортировка-процесс размещения заданного множества объектов в определенном порядке (убывания или возрастания)
  • (Д.Златопольский)
  • Сортировка- один из наиболее распространенных процессов современной обработки информации. Это распределение элементов множества по группам в соответствии с определенными правилами.
  • (Е.В.Андреева)
  • Методы сортировки
  • ПРОСТЫЕ
  • СЛОЖНЫЕ
  • Подсчетом
  • Вставками
  • Выбором
  • Обменом
  • Метод Шелла
  • С разделениями
  • Слияниями
  • Пирамидальная
  • СОРТИРОВКА ПОДСЧЕТОМ
  • Место каждого элемента в отсортированном массиве зависит от количества элементов, меньших его.
  • Например, если значение некоторого элемента исходного массива превышает значения четырех других, то его место в упорядоченной последовательности- пятое.
  • Следовательно, для сортировки надо для каждого элемента массива подсчитать к-во эл-тов, меньших его, и затем разместить каждый рассмотренный элемент на соответствующем месте в новом, специально созданном , массиве.
  • Исходный массив
  • 12
  • 32
  • 5
  • 6
  • 19
  • 20
  • 3
  • 10
  • 3
  • 5
  • 6
  • 10
  • 12
  • 19
  • 20
  • 32
  • Упорядоченный массив
  • 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] <a [j]
  • то {увеличиваем значение к для j-го элемента}
  • k [j]:= k [j] +1
  • иначе {увеличиваем значение k для i-го элемента}
  • k [i]:= k [i] +1
  • все
  • кц
  • кц
  • {размещаем все элементы массива а на соответствующих им местах в массиве b
  • нц для I от 1 до n
  • b [k [i] + 1]:=a [i] {позиция в массиве больше на 1 к-ва меньших по в-не числ}
  • кц
  • кон
  • СОРТИРОВКА ВЫБОРОМ
  • Сначала в неупорядоченном массиве выбирается минимальный элемент.
  • Этот элемент исключается из дальнейшей обработки , а оставшаяся последовательность элементов принимается за исходную, и процесс повторяется до тех пор, пока все элементы не будут выбраны. Выбранный в исходном массиве минимальный элемент размещается на первом месте в новом массиве.
  • Однако если на втором просмотре исходного массива вновь найти минимальный элемент, то им окажется тот же самый элемент.
  • Чтобы исключить эту ситуацию, в исходном массиве вместо выбранного, записать число, заведомо превосходя-щее любой элемент исх.массива
  • алг.Сортировка выбором
  • {Находим минимальный элемент массива и его индекс}
  • 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]
  • кц
  • кон
  • Второй способ сортировки выбором
  • Рассмотренный вариант сортировки обладает двумя недостатками:
  • Требование дополнительного массива
  • Для нахождения минимального элемента и его индек-са на каждом проходе приходится просматривать все элементы массива
  • Указанные недостатки устраняются, если все изменения проводить в исходном массиве:
  • Найти минимальный элемент среди всех элементов массива и поменять его местами с первым элементом
  • Найти минимальный элемент среди второго, третьего и т.д. элементов массива и поменять его местами со вторым элементом и т.д.
  • ….
  • В данной разработке урока применяется именно этот способ
  • алг.Сортировка выбором
  • for i := 1 to Dreal - 1 do {i - позиция, в которую нужно записать}
  • begin Min1 := 999999; {нач. значение для поиска минимальный элемента }
  • 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;
  • СОРТИРОВКА ОБМЕНОМ
  • Метод «пузырька»
  • Метод, при котором все соседние элементы массива попарно сравниваются друг с другом и меняются местами, если предшествующий элемент больше последующего.
  • В результате максимальный элемент постепенно смещается вправо и в конце концов занимает свое место (которое он должен занимать в упорядоченном массиве –крайнее правое), после чего этот элемент исключается из дальнейшей обработки.
  • Затем процесс повторяется , и свое место занимает второй по величине элемент. Так продолжается до тех пор, пока весь массив не будет упорядочен.
  • Если последовательность сортируемых чисел расположить вертикально (где первый элемент исходного массива –внизу)
  • и проследить за перемещением элементов, то можно увидеть, что большие элементы ,
  • подобно пузырькам воздуха в воде, «всплывают» на соответствующую позицию.
  • Поэтому по аналогии эту сортировку называют «методом пузырька» или «пузырьковой сортировкой»
  • 54
  • 73
  • 73
  • 73
  • 73
  • 73
  • 65
  • 54
  • 65
  • 65
  • 65
  • 65
  • 11
  • 65
  • 54
  • 54
  • 54
  • 54
  • 22
  • 11
  • 47
  • 47
  • 47
  • 47
  • 47
  • 22
  • 11
  • 30
  • 30
  • 30
  • 73
  • 47
  • 22
  • 11
  • 22
  • 22
  • 17
  • 30
  • 30
  • 22
  • 11
  • 17
  • 30
  • 17
  • 17
  • 17
  • 17
  • 11
  • алг.Сортировка обменом. Метод «Пузырька»
  • 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-й этап: 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
  • 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
  • 7-й этап:
  • 12 15 23 36 38 74 80 62
  • 12 15 23 36 38 62 74 80
  • алг.Сортировка вставками(включениями)
  • 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;
  • end;
  • end;
  • end;
  • «Даже если бы сортировка была почти бесполезна, нашлась бы масса причин заняться ею!
  • Изобретательные методы сортировки говорят о том, что она и сама по себе интересна как объект исследования.»
  • Д.Кнут
  • ЛИТЕРАТУРА:
  • Е.В.Андреева Л.Л.Босова И.Н.Фалина
  • «Математические основы информатики»
  • 2. Д.М.Златопольский
  • «Программирование: типовые задачи, алгоритмы, методы»
  • 3. И.Г.Семакин
  • «Информатика» учебник для 10 класса профильный курс
  • 4. И.Г.Семакин А.П.Шестаков
  • «Основы программирования»