0:00
[МУЗЫКА]
Рассмотрим алгоритмы сортировки.
Первым делом мы должны понять, а что такое, собственно, сортировка.
Сортировка — это перестановка элементов массива в определённом порядке.
Например, я рассмотрю массив A, который состоит из шести элементов.
Если я произведу сортировку элементов этого массива по возрастанию,
то у меня самый маленький элемент будет на первом месте,
а на последнем месте будет самый большой.
И каждый следующий элемент у меня будет больше или равен предыдущему.
Если я произведу сортировку этого массива по убыванию,
то порядок следования элементов будет обратный.
Для того чтобы выполнить сортировку, существует множество алгоритмов.
Мы с вами рассмотрим два наиболее простых и попытаемся сравнить их между собой.
Начнём мы с алгоритма, который носит название метода установки.
В нём каждый элемент массива будет последовательно устанавливаться
на необходимое место.
Для этого он будет сравниваться со всеми следующими элементами,
которые расположены после него, и если эта пара элементов расположена в
неверном порядке, то будет происходить перестановка.
Для примера я возьму тот же самый массив и рассмотрю сортировку по возрастанию.
На первом шаге я беру первый элемент массива и сравниваю его со вторым.
И смотрю, верно ли, что эта пара расположена по возрастанию.
В данном случае это неверно, и я поменяю эти два элемента местами.
Теперь я продолжаю рассматривать элемент, расположенный на первом месте,
и дальше я сравниваю его с третьим элементом массива.
В этом случае перестановка не нужна потому что самый маленький элемент
у меня уже попал на первое место.
Дальше элемент с первого места сравнивается с элементами,
расположенными на четвёртом, пятом и шестом местах.
Здесь ничего переставлять не нужно.
И теперь я вижу, что на первом месте расположен элемент,
который там и должен быть.
Далее я беру второе место и начинаю сравнивать элемент,
расположенный на второй месте, со всеми элементами, кроме первого.
Итак, рассматриваю пару: второй и третий элемент.
Если я посмотрю на эту пару, то я вижу, что она не расположена по возрастанию,
следовательно, нужно поменять эти два элемента местами.
И дальше я продолжаю сравнивать второй элемент с последующими.
Дальше я сравниваю его с четвёртым — перестановка не нужна,
с пятым — тоже не нужна, и с шестым — тоже перестановка не нужна.
Теперь у меня два первых элемента занимают свои нужные места.
Теперь я рассматриваю третье место и начинаю элемент,
расположенный на третьем месте, сравнивать с элементами, которые следуют за ним.
То есть он будет сравниваться с элементами на четвёртом, пятом и шестом местах.
Двойку я сравниваю с 5 — эта пара расположена по возрастанию,
двойку я сравниваю с 3 — эта пара также расположена по возрастанию,
а вот пара 2 1 должна быть переставлена.
Переставляю эти два элемента, и теперь у меня уже три элемента заняли свои места.
Я продолжаю четвёртый элемент сравнивать, ну в данном случае, с пятым и шестым.
Пара 5 3 у меня не расположена по возрастанию,
то есть я должна её переставить, далее я рассматриваю пару 3 2.
Пара 3 2 у меня также должна поменяться.
И осталось у меня два последних элемента, 5 и 3.
Эта пара также не расположена по возрастанию,
значит, я должна эти два элемента переставить.
В результате применения этого метода мы с вами расположили все элементы массива по
возрастанию.
Теперь рассмотрим, как выглядит постановка задачи для этого алгоритма.
Нам дано количество элементов, и нам дан сам массив.
Результатом является тот же самый массив с той же самой длиной, но при этом
элементы этого массива у нас расположены в другом порядке, это обозначено A'.
Теперь я накладываю ограничения на исходные данные, длина
массива должна быть натуральным числом и не превышать максимально возможной длины.
И теперь я описываю связь.
Важно, что, когда мы описываем связь, мы описываем не метод решения задачи,
то есть как мы получим наш результат, а мы пишем,
какой именно результат будет у нас после применения нашего метода.
Для каждого i от 1 до n − 1 наш элемент будет меньше или равен следующему,
после того как мы завершили перестановки.
То есть наш массив упорядочен, и упорядочен он по возрастанию.
Теперь рассмотрим, как выглядит алгоритм, записанный на псевдокоде.
В начале я должна ввести исходные данные, и затем я должна организовать два цикла.
Первый цикл будет выбирать номер места,
на котором будет находиться первый элемент пары, то есть что мы будем сравнивать.
Этот цикл начинается от первого номера и заканчивается предпоследним.
Возникает законный вопрос: а почему не последним?
Потому что мы с вами помним, что когда мы выбрали некоторое место,
то мы сравниваем элементы со всеми последующими.
У предпоследнего элемента есть последующий элемент — это последний элемент,
а у самого последнего последующего элемента нету.
И потому наш цикл продолжается до n − 1.
Вторым циклом мы выбираем,
с чем, с каким элементом мы будем сравнивать наш данный элемент.
И теперь я рассматриваю пару и говорю, что если в этой паре элемент
с меньшим номером больше, чем элемент с большим номером, то нужна перестановка.
Алгоритм перестановки мы с вами уже изучали,
это перестановка через третью переменную.
Я беру третью переменную C и меняю местами два этих значения,
чтобы они располагались правильно.
Дальше я закрываю нашу условную конструкцию,
завершаю сначала вложенный цикл, потом я завершаю внешний цикл,
и потом я вывожу на экран результаты выполнения этого алгоритма.
Будет выведен массив, который будет уже упорядочен по возрастанию.
У этого метода есть некоторые особенности,
которые нам с вами важно знать для решения задач.
Во‐первых, если мы захотим сделать вместо сортировки по возрастанию сортировку по
убыванию, то нам достаточно будет просто поменять знак в сравнении наших элементов.
Если при сортировке по возрастанию знак был больше,
то при сортировке по убыванию он будет меньше.
Далее, мы должны знать, что у нас может
встретиться массив, который изначально уже упорядочен.
Если массив изначально уже упорядочен, то тогда метод установки
будет всё‐равно производить все сравнения всех пар,
такие же, как это было для неупорядоченного массива.
Иными словами говоря, количество сравнений в этом методе будет зависеть
только от длины массива, а не от того, как в нём расположены
элементы.
[МУЗЫКА]
[МУЗЫКА]
Ерохина Елена АльфредовнаСтарший преподаватель
