К.Ю. Поляков, Е.А. Ерёмин, 2013 Программирование на языке Паскаль § 64. Сортировка 1. - презентация

1 К.Ю. Поляков, Е.А. Ерёмин, Программирование на языке Паскаль § 64. Сортировка 1

2 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Что такое сортировка? 2 Сортировка – это расстановка элементов массива в заданном порядке. …по возрастанию, убыванию, последней цифре, сумме делителей, по алфавиту, … Алгоритмы: простые и понятные, но неэффективные для больших массивов метод пузырька метод выбора сложные, но эффективные «быстрая сортировка» (QuickSort) сортировка «кучей» (HeapSort) сортировка слиянием (MergeSort) пирамидальная сортировка время работы N

3 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырька (сортировка обменами) 3 Идея: пузырек воздуха в стакане воды поднимается со дна вверх. Для массивов – самый маленький («легкий» элемент перемещается вверх («всплывает») сравниваем два соседних элемента; если они стоят «неправильно», меняем их местами за 1 проход по массиву один элемент (самый маленький) становится на свое место 1-й проход:

4 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырька й проход: 3-й проход: й проход: Для сортировки массива из N элементов нужен N-1 проход (достаточно поставить на свои места N-1 элементов). !

5 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырька 5 1-й проход: for j:= N-1 downto 1 do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; for j:= N-1 downto 1 do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; 2-й проход: for j:= N-1 downto do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; for j:= N-1 downto do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; 2 единственное отличие!

6 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырька 6 for i:= 1 to N-1 do for j:= N-1 downto do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; for i:= 1 to N-1 do for j:= N-1 downto do if A[j+1]< A[j] then begin { поменять местами A[j] и A[j+1] } end; i Как написать метод «камня»? ? Как сделать рекурсивный вариант? ?

7 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод пузырьков 7 program bubbleSort; const N = 5; var A: array[1..N] of integer; i, j, c: integer; begin writeln ( 'Введите элементы массива:' ); for i:=1 to N do read ( A[i] ); for i:=1 to N-1 do for j:=N-1 downto i do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; writeln ( 'После сортировки: ' ); for i:=1 to N do write ( A[i], ' ' ); end. Программа>>>>>>

8 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод камня 8 program stoneSort; const N = 5; var A: array[1..N] of integer; i, j, c: integer; begin writeln ( 'Введите элементы массива:' ); for i:=1 to N do read ( A[i] ); for i:=1 to N-1 do for j:=1 to N-i do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; writeln ( 'После сортировки: ' ); for i:=1 to N do write ( A[i], ' ' ); end. Программа >>>>>>

9 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, program bubbleSort; const N = 5; var A: array[1..N] of integer; i, j, c: integer; begin writeln ( 'Введите элементы массива:' ); for i:=1 to N do read ( A[i] ); for i:=1 to N-1 do for j:=N-1 downto i do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; writeln ( 'После сортировки: ' ); for i:=1 to N do write ( A[i], ' ' ); end. program stoneSort; const N = 5; var A: array[1..N] of integer; i, j, c: integer; begin writeln ( 'Введите элементы массива:' ); for i:=1 to N do read ( A[i] ); for i:=1 to N-1 do for j:=1 to N-i do if A[j] > A[j+1] then begin c:=A[j]; A[j]:=A[j+1]; A[j+1]:=c; end; writeln ( 'После сортировки: ' ); for i:=1 to N do write ( A[i], ' ' ); end.

10 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 10 «A»: Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива. «B»: Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок. «С»: Напишите программу, которая сортирует массив по убыванию суммы цифр числа. Используйте функцию, которая определяет сумму цифр числа.

11 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод выбора (минимального элемента) 11 Идея: найти минимальный элемент и поставить его на первое место. for i:= 1 to N-1 do begin { найти номер nMin минимального элемента из A[i]..A[N] } if i <> nMin then begin { поменять местами A[i] и A[nMin] } end end; for i:= 1 to N-1 do begin { найти номер nMin минимального элемента из A[i]..A[N] } if i <> nMin then begin { поменять местами A[i] и A[nMin] } end end;

12 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод выбора (минимального элемента) 12 for i:= 1 to N-1 do begin if i <> nMin then begin { поменять местами A[i] и A[nMin] } end end; for i:= 1 to N-1 do begin if i <> nMin then begin { поменять местами A[i] и A[nMin] } end end; nMin:= i; for j:=i+1 to N do if A[j] < A[nMin] then nMin:= j; Как поменять местами два значения? ?

13 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод выбора 13 program selectSort; const N = 5; var A: array[1..N] of integer; i, j, c, nMin: integer; begin writeln ( 'Введите элементы массива:' ); for i:=1 to N do read ( A[i] ); for i:=1 to N-1 do begin nMin:= i; for j:=i+1 to N do if A[j] < A[nMin] then nMin:= j; if i <> nMin then begin c:= A[i]; A[i]:= A[nMin]; A[nMin]:= c; end end; writeln ( 'После сортировки: ' ); for i:=1 to N do write ( A[i], ' ' ); end. Программа >>>>>>

14 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 14 «A»: Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине. Пример: Массив: После сортировки:

15 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 15 «B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Пример: Массив: После сортировки: Различных чисел: 5 «C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

16 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка (QuickSort) 16 Ч.Э.Хоар Идея: выгоднее переставлять элементы, который находятся дальше друг от друга Для массива из N элементов нужно всего N/2 обменов! !

17 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 17 Шаг 2: переставить элементы так: при сортировке элементы не покидают « свою область»! Шаг 1: выбрать некоторый элемент массива X A[i] <= XA[i] >= X Шаг 3: так же отсортировать две получившиеся области Разделяй и властвуй (англ. divide and conquer) Медиана – такое значение X, что слева и справа от него в отсортированном массиве стоит одинаковое число элементов (для этого надо отсортировать массив…) Как лучше выбрать X? ?

18 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 18 Разделение: 1)выбрать средний элемент массива ( X=67 ) 2)установить L:=1, R:=N 3)увеличивая L, найти первый элемент A[L], который >= X (должен стоять справа) 4)уменьшая R, найти первый элемент A[R], который <= X (должен стоять слева) 5)если L<=R то поменять местами A[L] и A[R] и перейти к п. 3 иначе стоп

19 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка LR LR LR RL L > R : разделение закончено! !

20 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 20 program QuickSort; const N = 7; var A: array[1..N] of integer;... begin { заполнить массив } qSort(1, N); { сортировка } { вывести результат } end; program QuickSort; const N = 7; var A: array[1..N] of integer;... begin { заполнить массив } qSort(1, N); { сортировка } { вывести результат } end; Основная программа: глобальные данные

21 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 21 procedure qSort(nStart, nEnd: integer); var L, R, c, X: integer; begin if nStart >= nEnd then Exit; L:= nStart; R:= nEnd; X:= A[(L+R) div 2]; { или X:= A[L+random(R-L+1)] } while L <= R do begin { разделение } while A[L] < X do L:= L + 1; while A[R] > X do R:= R - 1; if L <= R then begin c:= A[L]; A[L]:= A[R]; A[R]:= c; L:= L+1; R:= R-1 end end; qSort(nStart, R); { рекурсивные вызовы } qSort(L, nEnd) end; procedure qSort(nStart, nEnd: integer); var L, R, c, X: integer; begin if nStart >= nEnd then Exit; L:= nStart; R:= nEnd; X:= A[(L+R) div 2]; { или X:= A[L+random(R-L+1)] } while L <= R do begin { разделение } while A[L] < X do L:= L + 1; while A[R] > X do R:= R - 1; if L <= R then begin c:= A[L]; A[L]:= A[R]; A[R]:= c; L:= L+1; R:= R-1 end end; qSort(nStart, R); { рекурсивные вызовы } qSort(L, nEnd) end;

22 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 22 N метод пузырька метод выбора быстрая сортировка 10000,24 с 0,12 с 0,004 с 50005,3 с 2,9 с 0,024 с с 34 с 0,068 с Сортировка массива случайных значений:

23 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, program selectSort; const N = 7; var A: array[1..N] of integer; i: integer; procedure qSort(nStart, nEnd: integer); var L, R, c, X: integer; begin { Exit не работает в АЛГО } if nStart >= nEnd then Exit; L:= nStart; R:= nEnd; X:= A[(L+R) div 2]; while L <= R do begin { разделение } while A[L] < X do L:= L + 1; while A[R] > X do R:= R - 1; if L <= R then begin c:= A[L]; A[L]:= A[R]; A[R]:= c; L:= L+1; R:= R-1 end; qSort(nStart, R); { рекурсивные вызовы } qSort(L, nEnd); end; begin A[1]:=78; A[2]:=6; A[3]:=82; A[4]:=67; A[5]:=55; A[6]:=44; A[7]:=34; writeln ( 'До сортировки:' ); for i:=1 to N do write ( A[i], ' ' ); qSort(1, N); writeln; writeln ( 'После сортировки: ' ); for i:=1 to N do write ( A[i], ' ' ); end. Программа >>>>>>

24 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 24 «B»: Напишите программу, которая сортирует массив и находит количество различных чисел в нем. Используйте алгоритм быстрой сортировки. Пример: Массив: После сортировки: Различных чисел: 5

25 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 25 «C»: Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода. «D»: Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).

26 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ 163, г. Санкт-Петербург ЕРЕМИН Евгений Александрович к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь

27 Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Источники иллюстраций иллюстрации художников издательства «Бином» 3. авторские материалы