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

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

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

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

Алгоритмизация и программирование, Паскаль, 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 единственное отличие!

Алгоритмизация и программирование, Паскаль, 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 Как написать метод «камня»? ? Как сделать рекурсивный вариант? ?

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод выбора (минимального элемента) 8 Идея: найти минимальный элемент и поставить его на первое место. 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;

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Метод выбора (минимального элемента) 9 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; Как поменять местами два значения? ?

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

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

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

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 14 Разделение: 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 иначе стоп

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

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 16 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; Основная программа: глобальные данные

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Быстрая сортировка 17 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;

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

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

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

К.Ю. Поляков, Е.А. Ерёмин, Программирование на языке Паскаль § 65. Двоичный поиск 21

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Двоичный поиск X = 7X = 7 X = 7X = 7 X < 8X < X > 4X > X > 6 1. Выбрать средний элемент A[c] и сравнить с X. 2. Если X = A[c], то нашли (стоп). 3. Если X < A[c], искать дальше в первой половине. 4. Если X > A[c], искать дальше во второй половине. 1. Выбрать средний элемент A[c] и сравнить с X. 2. Если X = A[c], то нашли (стоп). 3. Если X < A[c], искать дальше в первой половине. 4. Если X > A[c], искать дальше во второй половине.

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Двоичный поиск 23 A[1]A[N]A[N+1] LRс LсR X = LсR LR L = R-1 : поиск завершен! !

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Двоичный поиск 24 var L, R, c: integer;... L:= 1; R:= N + 1; { начальный диапазон } while L < R-1 do begin c:= (L+R) div 2; { нашли середину } if X < A[c] then R:= c { изменить диапазон } else L:= c; end; if A[L] = X then writeln('A[',L,']=',X) else writeln('Не нашли!') var L, R, c: integer;... L:= 1; R:= N + 1; { начальный диапазон } while L < R-1 do begin c:= (L+R) div 2; { нашли середину } if X < A[c] then R:= c { изменить диапазон } else L:= c; end; if A[L] = X then writeln('A[',L,']=',X) else writeln('Не нашли!')

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Двоичный поиск 25 N линейный поиск двоичный поиск скорость выше, чем при линейном поиске нужна предварительная сортировка Когда нужно применять? ? Число сравнений:

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 26 «A»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений. Пример: Массив: После сортировки: Введите число X: 2 Число 2 найдено. Количество сравнений: 2

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 27 «B»: Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве. Пример: Массив: После сортировки: Введите число X: 4 Число 4 встречается 2 раз(а). Пример: Массив: После сортировки: Введите число X: 14 Число 14 не встречается.

Алгоритмизация и программирование, Паскаль, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 28 «C»: Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Если такого числа нет, вывести число, ближайшее к X. Пример: Массив: После сортировки: Введите число X: 12 Число 12 найдено. Пример: Массив: После сортировки: Введите число X: 11 Число 11 не найдено. Ближайшее число 12.