Сортировка методом пузырька, выбором (Pascal) Кокарева Светлана Ивановна. - презентация

1

2 Сортировка методом пузырька, выбором (Pascal) Кокарева Светлана Ивановна

3 Общее понятие о массивах Предположим, что программа работает с большим количеством однотипных данных. Скажем около ста разных целых чисел нужно обработать, выполнив над ними те или иные вычисления. Как вы себе представляете 100 переменных в программе? И для каждой переменной нужно написать одно и тоже выражение вычисления значения? Это очень неэффективно. Есть более простое решение. Это использование такой структуры (типа) данных как массив. Массив представляет собой последовательность ячеек памяти, в которых хранятся однотипные данные. При этом существует всего одно имя переменной связанной с массивом, а обращение к конкретной ячейке происходит по ее индексу (номеру) в массиве. Нужно четко понимать, что индекс ячейки массива не является ее содержимым. Содержимым являются хранимые в ячейках данные, а индексы только указывают на них. Действия в программе над массивом осуществляются путем использования имени переменной, связанной с областью данных, отведенной под массив.

4 Массив - это именованная группа однотипных данных, хранящихся в последовательных ячейках памяти. Каждая ячейка содержит элемент массива. Элементы нумеруются по порядку, но необязательно начиная с единицы (хотя в языке программирования Pascal чаще всего именно с нее). Порядковый номер элемента массива называется индексом этого элемента.

5 Общее понятие о массивах Помним, все элементы определенного массива имеют один и тот же тип. У разных массивов типы данных могут различаться. Например, один массив может состоять из чисел типа integer, а другой – из чисел типа real. Индексы элементов массива обычно целые числа, однако могут быть и символами, а также описываться другими порядковыми типами. Массив можно создать несколькими способами. Обращение к определенному элементу массива осуществляется путем указания имени переменной массива и в квадратных скобках индекса элемента. Простой массив является одномерным. Он представляет собой линейную структуру.

6 Способы создания одномерных массивов var ch: array [1..11] of char; h: char; i: integer; begin for i := 1 to 11 do read (ch[i]); for i := 1 to 11 do write (ch[i]:3); readln end. В примере выделяется область памяти под массив из 11 символов. Их индексы от 1 до 11. В процессе выполнения программы пользователь вводит 11 любых символов (например, q, w, e, 2, t, 9, u, I, I, o, p), которые записываются в ячейки массива. Текущее значение переменной i в цикле for используется в качестве индекса массива. Второй цикл for отвечает за вывод элементов массива на экран.

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

8 Сортировка методом пузырька Алгоритм решения задачи: Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировка методом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: "метод пузырька"? Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно "всплывают" в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).

9 Сортировка методом пузырька Алгоритм и особенности этой сортировки таковы: 1. При первом проходе по массиву элементы попарно сравниваются между собой: первый со вторым, затем второй с третьим, следом третий с четвертым и т.д. Если предшествующий элемент оказывается больше последующего, то их меняют местами. 2. Не трудно догадаться, что постепенно самое большое число оказывается последним. Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается. 3. При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше. 4. На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе. 5. В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение. 6. После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива. 7. Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.). 8. При обмене элементов массива обычно используется "буферная" (третья) переменная, куда временно помещается значение одного из элементов.

10 Сортировка

11

12

13

14 Алгоритм сортировки методом пузырька

15 Программа на языке Паскаль: const m = 10; var arr: array[1..m] of integer; i, j, k: integer; begin randomize; write ('Исходный массив: '); for i := 1 to m do begin arr[i] := random(256); write (arr[i]:4); end; writeln; writeln; for i := 1 to m-1 do for j := 1 to m-i do if arr[j] > arr[j+1] then begin k := arr[j]; arr[j] := arr[j+1]; arr[j+1] := k end; write ('Отсортированный массив: '); for i := 1 to m do write (arr[i]:4); writeln; readln end

16 Сортировка выбором Задача: Требуется отсортировать массив по возрастанию. Алгоритм решения задачи: 1. Для этого можно воспользоваться следующим алгоритмом. 2. Найти максимальный элемент (max) в массиве (arr). 3. Поместить его на последнее место (j). 4.Элемент, находившийся в конце массива переместить на место, где прежде находился max. 5. Уменьшить просматриваемую область массива на единицу (j – 1). 6. Снова найти максимальный элемент в оставшейся области. 7. Поместить его в конец просматриваемой области массива. 8. и т.д.

17 Программа на языке Pascal const n = 10; var arr: array[1..n] of byte; max, id_max, i, j: byte; begin randomize; for i := 1 to n do begin arr[i] := random(256); write(arr[i]:4) end; writeln; j := n; while j > 1 do begin max := arr[1]; id_max := 1; for i := 2 to j do if arr[i] > max then begin max := arr[i]; id_max := i end; arr[id_max] := arr[j]; arr[j] := max; j := j - 1 end; for i := 1 to n do write(arr[i]:4); readln end.

18 Переходим к набору программ сортировки Обе сортировки должны быть реализованы обучающимися!!! Поняты и приняты на вооружение алгоритмы сортировки для решения задач программирования!