8_Сортировка массивов

1. Преподаватель Мельникова Татьяна Федоровна Тема: Алгоритмы сортировки одномерных массивов

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

Вопросы входного контроля
- Что можно сортировать?
- Для чего нужна сортировка

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

Сортировкой или упорядочением массива называется
расположение его элементов по возрастанию (или
убыванию).
Например, массив X из n элементов будет
отсортирован в порядке возрастания значений его
элементов,
если X1 ≤X2 ≤… ≤Xn,
и в порядке убывания,
если X1 ≥X2 ≥… ≥Xn.

4. Сортировка элементов в массиве

Сортировать можно:
Элементы массива
Символы в строке
Строки матрицы
Существует большое количество алгоритмов
сортировки, но все они базируются на трех основных:
сортировка обменом;
сортировка выбором;
сортировка вставкой.

5. Сортировка элементов в массиве

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

6. Сортировка элементов в массиве

Для сортировки методом выбора из разложенных на
столе карт выбирают самую младшую (старшую) карту и
держат ее в руках.
Затем из оставшихся карт вновь нужно выбрать
наименьшую (наибольшую) по значению карту и
поместить ее позади той карты, которая была
выбрана первой.
Этот процесс повторяется до тех пор, пока вся колода
не окажется в руках.
Так как каждый раз выбирается наименьшая (наибольшая)
по значению карта из оставшихся на столе карт, по
завершению процесса карты будут отсортированы по
возрастанию (убыванию).

7. Сортировка элементов в массиве

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

8. Сортировка методом «пузырька»

Сортировка методом «пузырька» является наиболее
известной. Ее популярность объясняется легким
названием и простотой алгоритма.
Если в воде находится пузырёк с воздухом, то он
постепенно поднимается наверх. Связано это явление с
силой Архимеда: плотность воздуха меньше плотности
воды. Сортировка "пузырьком" немного напоминает
описанный процесс.
Сортировка методом «пузырька» использует метод
обменной сортировки и основана на выполнении в
цикле операций сравнения и при необходимости обмена
соседних элементов.

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

• Просматриваются все пары рядом стоящих элементов
массива
(1 и 2, 2 и 3, 3 и 4 и т.д.)
• Если они расположены в неправильном порядке, они
меняются местами.
• Это правило действует до тех пор, пока все пары не
будут стоять в правильном порядке (то есть, по
возрастанию или убыванию).
Количество сравнений и обменов равно N2 , где N –
количество элементов в массиве.

10. Сортировка методом «пузырька»

11. Сортировка методом «пузырька»

12. Сортировка методом «пузырька»

13. Задание

Выполнить анализ алгоритма с массивом
a={7,4,6,5,3}

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

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

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

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

18. Сортировка вставкой

Сортировка вставкой заключается в том, что сначала
упорядочиваются два элемента массива.
Затем делается вставка третьего элемента в
соответствующее место по отношению к первым двум
элементам.
Четвертый элемент помещают в список из уже
упорядоченных трех элементов.
Этот процесс повторяется до тех пор, пока все
элементы не будут упорядочены.

19. Сортировка вставкой

Прежде чем приступить к составлению блок–схемы
рассмотрим следующий пример.
Пусть известно, что в массиве из восьми элементов
первые шесть уже упорядочены, а седьмой элемент
нужно вставить между вторым и четвертым.
Сохраним седьмой элемент во вспомогательной
переменной, так как показано на рисунке 10, а на его
место запишем шестой.
< <
<
<
<
;
<
<
<

20. Сортировка вставкой

Далее пятый переместим на место шестого,
четвертый на место пятого,
а третий на место четвертого,
тем самым, выполнив сдвиг элементов массива на одну
позицию вправо.
Записав содержимое вспомогательной переменной в
третью позицию, достигнем нужного результата.

21. Сортировка вставкой

22. Или 2 -Сортировка вставкой

23. Сортировка вставкой

Организуем цикл для просмотра всех элементов
массива, начиная со второго (блок 4).
Сохраним значение текущего i–го элемента во
вспомогательной переменной X, так как оно может быть
потеряно при сдвиге элементов (блок 5) и присвоим
переменной j значение индекса предыдущего (i–1)–го
элемента массива (блок 6).
Далее движемся по массиву влево в поисках элемента
меньшего, чем текущий и пока он не найден сдвигаем
элементы вправо на одну позицию.

24. Сортировка вставкой

Для этого организуем цикл (блок 7), который
прекратиться, как только будет найден элемент меньше
текущего.
Если такого элемента в массиве не найдется и
переменная j станет равной нулю, то это будет означать,
что достигнута левая граница массива, и текущий
элемент необходимо установить в первую позицию.
Смещение элементов массива вправо на одну позицию
выполняется в блоке 8, а изменение счетчика j в блоке 9.
Блок 10 выполняет вставку текущего элемента в
соответствующую позицию.

25. Метод слияния

Метод слияния используется тогда, когда нужно получить единую
упорядоченную последовательность из двух разных отсортированных
массивов.
Алгоритм (сортировка по неубыванию):
• Сравниваются первые элементы массивов.
Если меньше элемент массива1, то выписываем его как
первый элемент выходного массива , переходим в массиве 1 к
следующему элементу;
иначе
первым будет элемент из массива 2,
переходим в массиве 2 к следующему элементу.
• Так сравниваем все элементы.
• Если кончился массив 1, все элементы из массива 2
переписываем в выходной массив,
Если кончился массив 2, все элементы из массива 1
переписываем в выходной массив.

26. Метод слияния

27. Метод слияния

Даны два отсортированных по неубыванию массива.
Внести единую упорядоченность для этих массивов.
Используйте сортировку слиянием.
Для решения задачи:
• Введем количество элементов в массиве А
• Сгенерируем массив А случайным образом
• Введем количество элементов в массиве В
• Сгенерируем массив В случайным образом
• Отсортируем массивы методом «пузырька»
• Отсортируем массивы методом слияния
• Выведем результат

28. Метод слияния

29. Метод слияния

В алгоритме использованы подпрограммы:
Ввод одномерного массива Vvod()
Вывод одномерного массиваVivod()
Сортировка одномерного массива Sortpuz()
Слияние отсортированных массивов Sortsl
Задание
Составить алгоритмы указанных подпрограмм

30. Спасибо за внимание!