Порядок выполнения задания. 1 Цель занятия изучить методику выполнения алгоритмов соритировки и поиска элементов контейнеров.

ПЗ-13 Сортировка и поиск

1 Цель занятия изучить методику выполнения алгоритмов соритировки и поиска элементов контейнеров.

2 Краткие методические указания. Наш курс называется «Алгоритмы и алгоритмические языки», поэтому нам необходимо кроме изучения языка, например языка Питон, изучать и основные алгоритмы. В ПЗ-07 мы рассматривали алгоритмы подсчета суммы элементов бесконечного ряда слагаемых, и алгоритмы повторения действий заданное число раз – циклы while и for. В некоторых других заданиях изучали методику выбора из нескольких альтернатив. Наряду с этими алгоритмами необходимо рассмотреть алгоритмы поиска элементов с заданными свойствами и сортировки элементов в контейнерах. В языке Питон эти алгоритмы реализованы в виде методов для контейнеров и ими можно пользоваться для решения прикладных задач. Но мы, в этом ПЗ будем считать, в учебных целях, что эти методы не реализованы (запрещено их использовать) и будем описывать их реализацию в виде функций. Алгоритмы сортировки и поиска подробно описаны в специальном томе “Сортировка и поиск» знаменитой трилогии Д. Кнута [1]. Поиском называют алгоритм, который находит в контейнере элемент с заданными свойствами. Например, в ПЗ-09 мы находили в списке элементы, которые обладали заданными свойствами. Сортировкой называют размещение элементов в контейнере в заданном порядке. Отношение порядка проще всего определяется для числовых данных. Поэтому реализацию алгоритмов сортировки мы будем рассматривать на примерах списков, содержащих числовые значения, или строки, которые тоже можно сравнивать [2-88]. Алгоритм сортировки может быть описан следующим образом:

Рассматриваются элементы заданного типа itm размещенные в контейнере L. Требуется найти элемент mitm, обладающий заданными свойствами среди элементов контейнера L. Такими свойствами может обладать отношение порядка, определенное на элементах контейнера. Обычно такого типа свойствами обладают все элементы контейнера. Например, если контейнер состоит из чисел, то их свойствами является значение, которым обладают все числа. Поэтому алгоритм поиска, например наибольшего числа в списке L может быть таким:

П1 Положим mitm=L[0]

П2 Для всех элементов контейнера L будем выполнять

П2.1 Если очереднгой элемент контейнера itm больше mitm, то заменим значение в mitm на значение из itm.

П3 Вернуть значение mitm

В первом пункте этого алгоритма максимальному значению элемента mitm присваивается значение первого элемента, так как первый элемент тоже число и может быть самым большим. Различают три основных метода сортировки [1]:

1. сортировка обменом (метод «пузырька»),
2. сортировка выбором и
3. сортировка вставками.

Ниже кратко описана постановка задачи и алгоритм решения для перечисленных видов сортировки.

Сортировка обменом. В контейнере в процессе сравнения соседних пар элементов устраняются нарушения порядка, до тех пор, пока не станет этих нарушений. Рассматривается множество целых чисел А=(a₁,a₂,..,a_n). Требуется разместить элементы в порядке убывания (возрастания) их величины.

П1 До тех пор пока в множестве есть нарушения порядка размещения пар соседних элементов ai и a_i+1, менять местами соседние элементы, для всех 1£i£n-1.

Сортировка выбором. В множестве элементов находят минимальный (максимальный) элемент и меняют его местами с первым. Затем рассматривается массив без первого элемента и в нем снова ищется минимальный (максиальный) элемент и размещается в первом элементе нового множества (сокращенного множества). Такой процесс повторяется для всех элементов массива.

Рассматривается множество целых чисел А=(a₁,a₂,..,a_n). Требуется разместить элементы в порядке убывания (возрастания) их величины.

П1 Для i=1 до n с шагом 1 выполнять

П1.1 Найти в массиве от i-го до n-го элементов минимальный и поменять его местами с i-м

Сортировка вставками. В множестве рассматривается две части. Первая часть из i первых элементов упорядочена, а вторая, начиная с i+1- го элемента не упорядочена. i+1-й элемент вставляется в нужное место первой половины, и первая половина становится на один элемент длиннее. Процесс вставки повторяется.

Рассматривается множество целых чисел А={a₁,a₂,..,a_n}. Требуется разместить элементы в порядке убывания (возрастания) их величины.

П1 Для i=2 до n с шагом 1 повторять (Цикл вставки)

П1.1 Положим х=а_i а j=i-1. (Начальные установки для выполнения вставки)

П1.2 Пока j>0 и аj>x выполнять(Цикл переписи и вставки до места вставки)

П1.2.1 Менять местами a_j+1 и a_j

П1.2.2 Положим a_j+1 =х

П1.2.3 Положим j=j-1

 

Порядок выполнения задания

3.1 Изучить методику разработки процессов сортировки и поиска.

3.2 Разработать и отладить программу, которая вводит список данных заданного типа, печатает список, находит в списке минимальный элемент для четных номеров (максимальный элемент для нечетных номеров), реализует два метода сортировки указанные в задании. Все указанные действия должны быть описаны в виде функций, которые вызываются из меню. Номера методов сортировки 1- обменом, 2- выбором, 3- вставками.

3.3 Результаты работы для контрольных примеров должны быть реализованы в отчете.

i	Метод-1	Метод-2	Тип
	1- убв	2- воз	целое
	1- воз	2- убв	целое
	1- воз	3- убв	целое
	1- убв	3- воз	целое
	2- убв	3- воз	компл
	2- воз	3- убв	компл
	1- убв	2- воз	вещ
	1- воз	2- убв	вещ
	1- воз	3- убв	вещ
	1- убв	3- воз	вещ
	2- убв	3- воз	компл
	2- воз	3- убв	компл
	1- убв	2- воз	стр
	1- воз	2- убв	стр
	1- воз	3- убв	стр
	1- убв	3- воз	стр
	2- убв	3- воз	компл
	2- воз	3- убв	компл

 

Литература

1 Д Кнут. Искусство программирования. Т3 Сортировка и поиск.

2 Саммерфильд М. Программирование на Python 3. Подробное руководство. – Пер. с англ. – СПб.: Символ‑Плюс, 2009. – 608 с., ил.

3 https://pythonworld.ru/samouchitel-python - самоучитель для питона -электронный ресурс

Вопросы по теме занятия

1 Что реализует алгоритм поиска

2 Что реализует алгоритм сортировки.

4 Почему в алгоритме поиска значению искомого элемента можно вначале присвоить значение любого элемента контейнера.

5 Опишите указанный преподавателем алгоритм сортировки.