Простые методы сортировки

1. Лабораторная работа 3. Простые методы сортировки

Дисциплина : Численные методы и программирование
лектор
Шустрова Марина Леонидовна

2. Цель работы:

Приобрести понимание принципов работы простых методов сортировки,
научиться их реализовывать на практике

3. Задание:

1)Изучить теоретический материал,
2) Решить предложенные задачи в соответствии со своим вариантом
3) Сформировать отчет по лабораторной работе

4. Что такое массив?

Массив (в некоторых языках программирования также таблица, ряд,
матрица) — структура данных в виде набора компонентов (элементов
массива), расположенных в памяти непосредственно друг за другом.
Массивы могут быть
одномерными и многомерными,
могут содержать числовые, логические и символьные данные.
Характерной
их
особенностью
является принцип, в соответствии с
которым имя присваивается сразу
всех совокупности данных, при
этом обращение к конкретной
ячейке
массива
происходит
посредством
использования
индекса – порядкового номера
записи в общей совокупности
данных.

5. Индексация элементов массива

Индексы элементов массива – это их
порядковые номера.
Аналогично поездам, у которых номер
поезда – это имя массива, вагон – элемент
массива, а его индекс - аналог номера
вагона

6. Сортировка

Сортировка – расположение информации в
определенном порядке (упорядочивание)
Чаще всего используются следующие виды
сортировки:
по алфавиту
по номеру
в хронологическом порядке

7. Алгоритм сортировки

Алгоритм сортировки — это алгоритм для упорядочивания элементов в
списке.
В случае, когда элемент списка имеет несколько полей, поле, служащее
критерием порядка, называется ключом сортировки.
На практике в качестве ключа часто выступает
число, а в остальных полях хранятся какиелибо данные, никак не влияющие на работу
алгоритма.
Мы будем рассматривать алгоритмы
сортировок на массивах числовых данных

8. Алгоритмы сортировки

В настоящее время разработано великое множество различных алгоритмов
сортировки. В данном курса мы рассмотрим некоторые из них. Сейчас нас
интересуют простые методы (слева).
Простые методы сортировки
Сортировка пузырьком
Эффективные методы сортировки
Быстрая сортировка
Шейкерная сортировка
Сортировка слиянием
Сортировка расческой
Пирамидальная сортировка
Сортировка чётно-нечётная
Простая сортировка
Сортировка вставками
Сортировка выбором

9. Сортировка пузырьком

Реализуется последовательное
сравнение двух соседних
элементов.
Если левый элемент больше
правого, они меняются
местами.
Алгоритм повторяется, пока все
элементы не встанут на свои
места

10. Задание1.1:

Проанализировав алгоритм сортировки «Пузырьком», составьте блоксхему работы данного метода
Результат занесите в отчет по лабораторной работе

11. Задание 1.2

Составьте программу, реализующую метод сортировки пузырьком.
!!!Массивы у всех будут разными, разной длины и с разными значениями.
Можно использовать для создания массива функцию *random
Сколько итераций потребовалось вам для сортировки вашего массива?
Ответ на вопрос, листинг программы и поитерационный результат расчета
занесите в отчет по лабораторной работе

12. Быстро ли работает алгоритм?

13. Быстро ли работает алгоритм?

14. А причем здесь черепашки?

Помните сказку о Кролике и Черепахе? Она нам
сейчас пригодится.
Небольшая предыстория. В 1980 году Влодзимеж
Добосиевич пояснил, почему пузырьковая и
производные от неё сортировки работают так
медленно.
Это всё из-за черепашек. «Черепахи» —
небольшие по значению элементы, которые
находятся в конце списка. Поскольку алгоритм
подразумевает перенос больших элементов в
конец списка, они быстро находят свое место.
Небольшие элементы находят свое место
медленно, меняя свое положение на 1 позицию
в каждой итерации.
Как Вы, возможно, заметили пузырьковые
сортировки ориентированы на «кроликов» –
больших по значению элементов в начале
списка. Они довольно быстро перемещаются к
конце списка. А вот медлительные
пресмыкающиеся на старт ползут неохотно.

15. Шейкерная сортировка

Шейкерная сортировка работает немного быстрее, чем пузырьковая, поскольку
по массиву в нужных направлениях попеременно мигрируют и максимумы и
минимумы.
Шейкерная сортировка- Вариация сортировки пузырьком.
Также ее называют сортировка перемешиванием, она же коктейльная сортировка.
Начинается процесс как в «пузырьке»: максимум перемещается в конец массива.
После этого идём в обратную сторону, при этом уже перенося в начало не максимум, а
минимум.
Отсортировав в массиве первый и последний элементы, снова делаем разворачиваемся,
и т.д.. Заканчиваем процесс, оказавшись в середине списка.

16. Задание2.1:

Проанализировав алгоритм сортировки «Шейкер», составьте блоксхему работы данного метода
Результат занесите в отчет по лабораторной работе

17. Задание 2.2

Составьте программу, реализующую метод шейкерной сортировки.
Массив нужно использовать тот же, что и в предыдущем задании
Сколько итераций теперь потребовалось вам для сортировки вашего
массива?
Ответ на вопрос, листинг программы и результат расчета занесите в отчет по
лабораторной работе

18. Быстрее ли работает шейкерный метод?

19. Чётно-нечётная сортировка

Тоже вариация «Пузырька»
Идея планомерного обхода слева-направо, но только сделаем шире
шаг.
На первом проходе элементы с нечётным ключом сравниваем с
соседями на чётных местах (1-й сравниваем со 2-м, затем 3-й с 4-м, 5й с 6-м и так далее).
Затем наоборот – «чётные по счёту» элементы сравниваем/меняем с
«нечётными». Затем снова «нечёт-чёт», потом опять «чёт-нечет».
Процесс останавливается тогда, когда после подряд двух проходов по
массиву («нечётно-чётному» и «чётно-нечётному») не произошло ни
одного обмена.

20. Задание 3.1(для студентов с нечетным номером по списку):

Проанализировав алгоритм четно-нечетной сортировки , составьте
блок-схему работы данного метода
Результат занесите в отчет по лабораторной работе

21. Задание 3.2 (для студентов с нечетным номером по списку):

Составьте программу, реализующую метод четно-нечетной
сортировки.
Массив, конечно, снова то же
Сколько итераций теперь потребовалось вам для сортировки вашего
массива?
Ответ на вопрос, листинг программы и результат расчета занесите в
отчет по лабораторной работе

22. Сортировка расчёской

Её идея состоит в том, чтобы «устранить» элементы с небольшими значения в
конце массива, которые замедляют работу алгоритма.
В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются
соседние элементы.
Основная идея «расчёски» в том, чтобы первоначально брать достаточно
большое расстояние между сравниваемыми элементами и по мере
упорядочивания массива сужать это расстояние вплоть до минимального.
Таким образом, мы как бы причёсываем массив, постепенно разглаживая на
всё более аккуратные пряди.
Первоначальный разрыв нужно выбирать не случайным образом, а с учётом
специальной величины — фактора уменьшения, оптимальное значение
которого равно 1,247. Сначала расстояние между элементами будет равняться
размеру массива, поделённому на 1,247; на каждом последующем шаге
расстояние будет снова делиться на фактор уменьшения — и так до окончания
работы алгоритма или пока разность индексов не достигнет единицы. В этом
случае массив досортировывается обычным пузырьком.

23. Задание 4.1(для студентов с чётным номером по списку):

Проанализировав алгоритм сортировки расческой, составьте блоксхему работы данного метода
Результат занесите в отчет по лабораторной работе

24. Задание 4.2 (для студентов с чётным номером по списку):

Составьте программу, реализующую метод сортировки расческой.
Да, массив опять тот же
Сколько итераций теперь потребовалось вам для сортировки вашего
массива?
Ответ на вопрос, листинг программы и результат расчета занесите в
отчет по лабораторной работе

25. Сортировка вставками

При сортировке вставками массив постепенно перебирается слева
направо. При этом каждый последующий элемент размещается так, чтобы
он оказался между ближайшими элементами с минимальным и
максимальным значением.
Элементарный пример: При игре в дурака, вы тянете из колоды карту и
вставляете ее в соответствующее место по возрастанию в имеющихся у
вас картах. Или
в магазине вам дали сдачу 550 рублей- одна купюра 500, другая 50.
Заглядываете в кошелек, а там купюры достоинством 10, 100, 1000. Вы
вставляете купюру достоинсвом 50р. между купюрами достоинством 10р и
100р, а купюру в 500 рублей между купюрами 100р и 1000р. Получается 10,
50, 100, 500, 1000 –
Таким образом с каждым шагом алгоритма, вам необходимо
отсортировать подмассив данных и вставить значение в нужное место.

26. Задание 5.1(для студентов с нечётным номером по списку):

Проанализировав алгоритм сортировки вставками, составьте блоксхему работы данного метода
Результат занесите в отчет по лабораторной работе

27. Задание 5.2 (для студентов с нечётным номером по списку):

Составьте программу, реализующую метод сортировки вставками.
И у вас массив тоже тот же
Сколько итераций теперь потребовалось вам для сортировки вашего
массива?
Ответ на вопрос, листинг программы и результат расчета занесите в
отчет по лабораторной работе

28. Сортировка выбором

Является одним из самых простых алгоритмов сортировки массива. Смысл в том, чтобы
идти по массиву и каждый раз искать минимальный элемент массива, обменивая его с
начальным элементом неотсортированной части массива. На небольших массивах
может оказаться даже эффективнее, чем более сложные алгоритмы сортировки, но в
любом случае проигрывает на больших массивах.
Число обменов элементов по сравнению с "пузырьковым" алгоритмом N/2, где N - число
элементов массива.
Алгоритм:
1. Находим минимальный элемент в массиве.
2. Меняем местами минимальный и первый элемент местами.
3. Опять ищем минимальный элемент в неотсортированной части массива
4. Меняем местами уже второй элемент массива и минимальный найденный, потому
как первый элемент массива является отсортированной частью.
5. Ищем минимальные значения и меняем местами элементы, пока массив не будет
отсортирован до конца.

29. Задание 6.1(для студентов с чётным номером по списку):

Проанализировав алгоритм сортировки выбором, составьте блоксхему работы данного метода
Результат занесите в отчет по лабораторной работе

30. Задание 5.2 (для студентов с чётным номером по списку):

Составьте программу, реализующую метод сортировки выбором.
Сколько итераций теперь потребовалось вам для сортировки вашего
массива?
Массив.. Ну, вы поняли
Ответ на вопрос, листинг программы и результат расчета занесите в
отчет по лабораторной работе

31. Теперь составляем таблицу

Задание
Метод
Количество
итераций
1
2
3 или 4
И проводим сравнительный анализ результатов
Да, письменно и в отчете.
Этот анализ мы записываемы в вывод по лабораторной работе

32. Дополните отчет

Титульным листом
Целью и вариантом задания ( нечётные – 1, четные – 2)

33. …и можно отправлять на проверку