Изучение нового материала
|
ткрытие новых знаний. Объяснение учителя
Сортировка – это расстановка элементов массива в заданном порядке (по возрастанию, убыванию, последней цифре, сумме делителей, …).
Задача: переставить элементы массива в порядке возрастания.
Алгоритмы:
сортировка обменом – «пузырьковая»
сортировка выбором
сортировка вставками
сортировка подсчетом
8 методов сортировок Python и их процесс работы
Пузырьковая сортировка(Bubble Sort Algorithm)
Выборочная сортировка(Selection Sort Algorithm)
Сортировка вставками(Insertion Sort Algorithm)
Быстрая сортировка(Quick Sort Algorithm)
Сортировка слиянием(Merge Sort Algorithm)
Сортировка по сегментам(Bucket Sort Algorithm)
Сортировка Шелла(Shell Sort Algorithm)
Будем исходить из того, что сначала лучше делать перестановки элементов массива на большом расстоянии. Предположим, что у нас есть п элементов и известно, что они уже отсортированы в обратном порядке. Тогда за n/2 обменов можно отсортировать их как нужно — сначала поменять местами первый и последний, а затем последовательно двигаться с двух сторон к центру. Хотя это справедливо только тогда, когда порядок элементов обратный, подобная идея положена в основу алгоритма Quicksort.
Пусть дан массив А из n элементов. Выберем сначала наугад любой элемент массива (назовем его X). Обычно выбирают средний элемент массива, хотя это необязательно. На первом этапе мы расставим элементы так, что слева от некоторой границы находятся все числа, меньшие или равные X, а справа — большие или равные X:
Заметим, что элементы, равные X, могут находиться в обеих частях.
Теперь элементы расположены так, что ни один элемент из первой части при сортировке не окажется во второй части и наоборот. Поэтому далее достаточно отсортировать отдельно каждую часть массива. Такой подход называют «разделяй и властвуй» (англ, divide and conquer).
Лучше всего выбирать X так, чтобы в обеих частях было равное количество элементов. Такое значение X называется медианой массива. Однако для того, чтобы найти медиану, надо сначала отсортировать массив, т. е. заранее решить ту самую задачу, которую мы собираемся решить этим способом. Поэтому обычно в качестве X выбирают средний элемент массива.
Сначала будем просматривать массив слева до тех пор, пока не обнаружим элемент, который больше X (и, следовательно, должен стоять справа от X). Затем просматриваем массив справа до тех пор, пока не обнаружим элемент, меньший X (он должен стоять слева от X). Теперь поменяем местами эти два элемента и продолжим просмотр до тех пор, пока два «просмотра» не встретятся где-то в середине массива. В результате массив окажется разбитым на 2 части: левую со значениями, меньшими или равными X, и правую со значениями, большими или равными X. На этом первый этап («разделение») закончен. Затем такая же процедура применяется к обеим частям массива до тех пор, пока в каждой части не останется по одному элементу (таким образом, массив будет отсортирован).
Чтобы понять сущность метода, рассмотрим пример. Пусть задан массив:
Выберем в качестве X средний элемент массива, т. е. 67. Найдем первый слева элемент массива, который больше или равен X и должен стоять во второй части. Это число 78. Обозначим индекс этого элемента через L. Теперь находим самый правый элемент, который меньше X и должен стоять в первой части. Это число 34. Обозначим его индекс через R:
Теперь поменяем местами эти два элемента. Сдвигая переменную L вправо, a R — влево, находим следующую пару, которую надо переставить. Это числа 82 и 44:
Следующая пара элементов для переноски - числа 67 и 55:
После этой перестановки дальнейший поиск приводит к тому, что переменная L становится больше R:
В результате все элементы массива, расположенные левее A[L], меньше или равны X, а все элементы правее А[R] — больше или равны X.
Теперь нужно применить тот же алгоритм к двум полученным частям массива: первая часть — с 1-го элемента до R-ro элемента, вторая часть — с L-ro до последнего элемента. Как вы знаете, такой приём называется рекурсией.
Чтобы не загромождать решение деталями оформления, которые сильно различаются в школьном алгоритмическом языке и в Паскале, предположим, что в нашей программе один глобальный массив А с индексами от 1 до N, который нужно сортировать. Термин «глобальный» означает, что массив доступен всем процедурам и функциям. Глобальные данные объявляются выше основной программы:
Тогда процедура сортировки принимает только два параметра, ограничивающие её «рабочую зону»: nStart — номер первого элемента, и nEnd — номер последнего элемента. Если nStart = nEnd, то в «рабочей зоне» один элемент и сортировка не требуется, т. е. нужно выйти из процедуры. В этом случае рекурсивные вызовы заканчиваются.
Приведём полностью процедуру быстрой сортировки на школьном алгоритмическом языке:
Для того чтобы отсортировать весь массив, нужно вызвать эту процедуру так:
qSort(l, N)
Скорость работы быстрой сортировки зависит от того, насколько удачно выбирается вспомогательный элемент X. Самый лучший случай — когда на каждом этапе массив делится на две равные части. Худший случай — когда в одной части оказывается только один элемент, а в другой — все остальные. При этом глубина рекурсии достигает N, что может привести к переполнению стека (нехватке стековой памяти).
Для того чтобы уменьшить вероятность худшего случая, в алгоритм вводят случайность: в качестве X на каждом шаге выбирают не середину рабочей части массива, а элемент со случайным номером:
X:=А[irand(L,R)]
В таблице 8.1 сравнивается время сортировки (в секундах) массивов разного размера, заполненных случайными значениями, с использованием трёх изученных алгоритмов.
Как показывают эти данные, преимущество быстрой сортировки становится подавляющим при увеличении N.
Сортировка выбором в Питоне
Суть сортировки
В неотсортированном подмассиве ищется локальный максимум (минимум).
Найденный максимум (минимум) меняется местами с последним (первым) элементом в подмассиве.
Если в массиве остались неотсортированные подмассивы
Шаги к правильному решению
Создадим функцию selection_sort, которая принимает на вход список.
Внутри функции создадим цикл с переменной i, которая будет исчисляться с 0 до (длины списка - 1)
Создадим переменную smallest = i.
Создадим внутренний цикл с переменной j от i + 1 до (длины списка - 1).
Внутри этого цикла, если j-элемент (элемент под индексом j) меньше, чем элемент с индексом smallest, тогда устанавливаем smallest = j.
После завершения внутреннего цикла меняем местами элементы под индексами i и smallest.
Код программы в Питоне:
def selection_sort(alist):
for i in range(0, len(alist) - 1):
smallest = i
for j in range(i + 1, len(alist)):
if alist[j] < alist[smallest]:
smallest = j
alist[i], alist[smallest] = alist[smallest], alist[i]
alist = input('Enter the list of numbers: ').split()
alist = [int(x) for x in alist]
selection_sort(alist)
print('Sorted list: ', end='')
print(alist)
Проверка знаний: ученкам стоит ввести порядок код программы ссылаясь примерам.
Следующая игра «Вызов себе» является логического типа и цель этой игры это запомнить теги слов, которые мы использовали на данный урок.
Дескрипторы:
- умеют различать виды сортировок в Питоне;
- умеют рассказать как работает метод прямого выбора по возрастанию;
- узнали как работает циклы for, while и if в метод прямого выбора;
- умеют писать код программы массив и одномерный массив.
Задание
Теоретическая часть:
Уровень А.
1. Записать в тетради названия методов сортировки, не менее 6 (презентация 10-8Pb_Паскаль-II/параграфы 64,65/ слайды 36, 46, 59).
2. Записать в тетради фрагменты программы простых методов сортировки: метод пузырь и метод выбора (презентация 10-8Pb_Паскаль-II/параграфы 64,65/ слайды 40, 43).
Уровень В, С.
3. Оценить эффективность методов сортировки, заполнив сравнительную таблицу по материалам презентации в тетради (презентация 10-8Pb_Паскаль-II/параграфы 64,65):
|
Анализируют правило 1-3
Ознакамливаются с методами решения
Разбирают совместно с учителем понятие
|
Словесная оценка учителя
. Взаимооценивание
Стратегия «Стикер
|
Критическое мышление.
Саморегулируемое обучение (самонаправленность в процессе работы над заданиями).
|
Скачать 90.53 Kb.