А что, собственно, нужно выбирать в алгоритме сортировки выбором?

Метод сортировки выбором базируется на очень популярной операции – поиск наименьшего/наибольшего элемента. Если вы фундаментально понимаете принцип работы подобного поиска, то вам не составит большого труда разобраться с алгоритмом сортировки выбором с первого раза.

Но если вы хотите понять данный алгоритм на самом аутентичном уровне, то вам придется исследовать такие характеристики алгоритма, как устойчивость, естественность поведения, скорость выполнения, количество сравнений.

Нет никакой возможности написать исчерпывающую обзорную статью, повествующую обо всех этих характеристиках, так как количество различных хитросплетений просто зашкаливает.

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

Также вы должны уметь менять местами значения двух заданных элементов одномерного массива. Разумеется, это простейшая операция, которой владеет практически каждый школьник, сдающий ОГЭ или ЕГЭ по информатике и ИКТ.

Мультимедийный ролик, презентующий метод сортировки выбором

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

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

Программирование алгоритма сортировки выбором на языке Паскаль

Разумеется, я не мог не поделиться программным кодом, реализующим алгоритм сортировки выбором. В качестве базового языка программирования был выбран язык Паскаль, так как именно данный язык является наиболее популярным в процессе обучения у школьников и студентов.

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

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

Условие задачи звучит так:

Дан одномерный массив, состоящий из $10$ элементов целого типа. Заполнение элементов массива производится случайным образом из отрезка $[-40\ …\ 40]$. Необходимо отсортировать заданный массив сортировкой выбором по возрастанию значения элементов. Вывести элементы массива до и после сортировки на экран пользователя.

Анализ сортировки выбором на устойчивость

Является ли сортировка выбором устойчивой?

➡ Напомню, что значит «устойчивая сортировка»! Сортировка является устойчивой, если после сортировки данных, элементы, имеющие одинаковые ключи, не поменяли своего первоначального взаимного расположения.

Для исследования устойчивости сортировки выбором обязательно нужно иметь элементы, которые имеют одинаковые значения/ключи. Я рассмотрю следующий одномерный статический целочисленный массив, состоящий из $8$ элементов, который подвергнем сортировке выбором по возрастанию.

6 -17 8 19 8 13 8 -6 значение
1 2 3 4 5 6 7 8 индекс

Данный массив содержит $3$ элемента с одинаковыми значениями равными $8$ (индексы этих элементов: $3$, $5$ и $7$). Чтобы как-то различать эти элементы давайте пронумеруем их:

6 -17 $8_1$ 19 $8_2$ 13 $8_3$ -6 значение
1 2 3 4 5 6 7 8 индекс

Если алгоритм сортировки выбором является устойчивым, то после сортировки элементы массива должны быть расставлены таким образом:

-17 -6 6 $8_1$ $8_2$ $8_3$ 13 19 значение
1 2 3 4 5 6 7 8 индекс

💡 Сейчас я сделаю несколько прогонов сортировки выбором на заданном наборе чисел.

Итерация №1. Минимальный элемент $-17$. Меняем местами элементы со значениями $-17$ и $6$. Массив принял такой вид:

-17 6 $8_1$ 19 $8_2$ 13 $8_3$ -6 значение
1 2 3 4 5 6 7 8 индекс

Итерация №2. Минимальный элемент $-6$. Меняем местами элементы со значениями $-6$ и $6$. Массив принял такой вид:

-17 -6 $8_1$ 19 $8_2$ 13 $8_3$ 6 значение
1 2 3 4 5 6 7 8 индекс

Итерация №3. Минимальный элемент $6$. Меняем местами элементы со значениями $6$ и $8_1$. Массив принял такой вид:

-17 -6 6 19 $8_2$ 13 $8_3$ $8_1$ значение
1 2 3 4 5 6 7 8 индекс

Что я вижу! Элемент со значением $8_1$ «улетел» в конец массива, следовательно, у него уже не будет шансов оказаться раньше своих элементов-близнецов со значениями $8_2$ и $8_3$ после окончания процесса сортировки выбором.

-17 -6 6 19 $8_2$ 13 $8_3$ $8_1$ значение
1 2 3 4 5 6 7 8 индекс

➡ Следовательно, алгоритм сортировки выбором является неустойчивым! Разумеется, что иногда устойчивость наблюдается, но это лишь иногда!

Анализ сортировки выбором на естественность

Является ли сортировка выбором естественной?

➡ Напомню, что значит «естественная сортировка»! Сортировка является естественной, если процесс упорядочивания происходит более эффективно на заранее частично упорядоченных данных.

Давайте посмотрим на ядро алгоритма сортировки выбором:

Очевидно, что количество итераций не изменится, если на вход будет подан, пускай, даже полностью отсортированный массив. В любом случае программа будет $(n — 1)$ раз находить минимальный элемент в неотсортированной части и менять его с первым элементом из неотсортированной части.

➡ Следовательно, алгоритм сортировки выбором не является естественным. То есть данный способ сортировки не становится более эффективным, когда на вход подаются полностью или частично упорядоченные данные.

P.S. Единственное, на что стоит обратить внимание — это уменьшение количества присваиваний в процессе поиска минимального элемента в неотсортированной части. Но при этом количество сравнений не меняется!

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

Сортировка выбором является внешней или внутренней сортировкой?

Так как сортировка выбором не требует в процессе своей работы использования вспомогательной памяти, как оперативной, так и файловой, то, очевидно, что данная сортировка является внутренней.

➡ Другими словами, чтобы упорядочить данные сортировкой выбора достаточно лишь иметь массив с данными!

Остались какие-то сомнения, вопросы, недопонимания?

Если, ознакомившись с данной публикацией, просмотрев мультимедийное объяснение и исследовав программный код, у вас все равно осталось какое-то чувство неудовлетворенности, то смело звоните мне на мобильный телефон и задавайте любые тематические вопросы относительно алгоритма сортировки выбором.

💡 Уже на протяжении $15+$ лет я готовлю школьников к успешной сдаче ЕГЭ по информатике, а студентам помогаю при подготовке к экзаменам по программированию и выполнению различных студенческих работ по программированию.

➡ Чтобы получить качественную помощь по разделам IT-сферы звоните мне по номеру 8(926) 610 — 61 — 95 или пишите на почту proglabs@mail.ru.