Урок 77. Сортировка массивов методом выбора

   ⁄ 

 Обновлено 27 Авг 2017

  ⁄   

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

Сортировка массива может сделать поиск внутри массива более эффективным не только для людей, но и для компьютеров. Например, рассмотрим случай, когда нам нужно узнать, отображается ли определенное имя в списке имен. Чтобы это узнать, нужно проверить каждый элемент в массиве на соответствие с нашим значением. Поиск в массиве с множеством элементов может оказаться слишком неэффективным (затратным).

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

Не секрет, что есть алгоритмы поиска внутри отсортированных массивов и получше. Используя простой алгоритм, мы можем искать определенный элемент в отсортированном массиве, содержащем 1 000 000 элементов, используя только 20 сравнений! Недостатком, конечно же, является то, что сортировка массива с таким огромным количеством элементов — дело сравнительно очень затратное, и часто это не стоит того, чтобы выполнить поисковый запрос один раз.

В некоторых случаях сортировка массива делает поиск ненужным. Например, мы ищем лучший результат выполнения теста. Если массив не отсортирован, то нам придется просмотреть каждый элемент массива, чтобы найти наивысшую оценку. Если же массив отсортирован, то наивысшая оценка будет находиться либо на первой позиции, либо на последней (в зависимости от метода сортировки массива: в порядке возрастания или убывания), поэтому нам не нужно искать вообще!

Как работает сортировка

Сортировка обычно выполняется путем повторного сравнения пар элементов массива и их замены, если они отвечают определенным критериям. Порядок, в котором эти элементы сравниваются, зависит от того, какой алгоритм сортировки используется. Критерии состоят из того, как будет сортироваться массив (например, в порядке возрастания или убывания).

Чтобы поменять два элемента местами, мы можем использовать функцию std::swap() из стандартной библиотеки C++, которая определена в заголовочном файле <algorithm>. В C++11, в целях эффективности, std::swap() был перенесен в заголовочный файл <utility>.

Результат:

Before swap: a = 3, b = 5
After swap: a = 5, b = 3

После выполнения замены значения переменных a и b поменялись местами.

Сортировка методом выбора

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

Для сортировки массива от наименьшего до наибольшего элемента методом выбора выполняются следующие шаги:

1. Начиная с элемента под индексом 0, ищем в массиве наименьшее значение.

2. Найденное значение меняем местами с нулевым элементом.

3. Повторяем шаги 1 и 2 уже для следующего индекса в массиве.

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

Вот пример работы этого алгоритма в массиве с 5-ью элементами:

{ 30, 50, 20, 10, 40 }

Сначала ищем наименьший элемент, начиная с индекса 0:

{ 30, 50, 20, 10, 40 }

Затем меняем местами наименьший элемент с элементом под индексом 0:

10, 50, 20, 30, 40 }

Теперь, когда первый элемент отсортирован, мы его игнорируем. Ищем следующий наименьший элемент, но уже начиная с индекса 1:

10, 50, 20, 30, 40 }

И меняем его местами с элементом под индексом 1:

102050, 30, 40 }

Теперь мы можем игнорировать первые два элемента. Ищем следующий наименьший элемент, начиная с индекса 2:

1020, 50, 30, 40 }

И меняем его местами с элементом под индексом 2:

10203050, 40 }

Ищем следующий наименьший элемент, начиная с индекса 3:

102030, 50, 40 }

И меняем его местами с элементом под индексом 3:

1020304050 }

Ищем следующий наименьший элемент, начиная с индекса 4:

1020304050 }

И меняем его местами с элементов под индексом 4 (самозамена — ничего не делаем):

10203040 50 }

Готово!

{ 10, 20, 30, 40, 50 }

Обратите внимание, последнее сравнение всегда будет одиночным, (т. е. сам с собой), что является излишним, поэтому фактически мы можем остановить выполнение сортировки перед последним элементом в массиве.

Сортировка методом выбора в C++

Вот как этот алгоритм реализован в C++:

Наиболее запутанной частью этого алгоритма является цикл внутри другого цикла (так называемый вложенный цикл). Внешний цикл (startIndex) перебирает элементы один за другим (по очереди). В каждой итерации внешнего цикла внутренний цикл (currentIndex) используется для поиска наименьшего элемента среди элементов, которые остались в массиве (начиная с startIndex + 1). smallestIndex отслеживает индекс наименьшего элемента, найденного внутренним циклом. Затем smallestIndex меняется значением с startIndex. И наконец, внешний цикл (startIndex) передает этот элемент, и процесс повторяется.

Подсказка: Если у вас возникли проблемы с пониманием того, как работает вышеуказанная программа, попробуйте записать её выполнение на листе бумаги. Запишите начальные (неотсортированные) элементы массива горизонтально в строке в верхней части листа. Нарисуйте стрелки, указывающие, какие элементы являются startIndex, currentIndex и smallestIndex на данный момент. Прокрутите выполнение программы вручную и перерисуйте стрелки по мере изменения индексов. После каждой итерации внешнего цикла нарисуйте новую строку, показывающую текущее состояние массива (расположение его элементов).

Сортировка имен выполняется с помощью того же алгоритма. Просто измените тип массива из int в std::string и инициализируйте его с помощью соответствующих значений.

std::sort

Поскольку сортировка массивов настолько распространена, то стандартная библиотека C++ предоставляет встроенную функцию сортировки — std::sort. Она находится в заголовке <algorithm> и вызывается следующим образом:

Тест

1. Напишите на листе бумаги выполнение сортировки методом выбора в следующем массиве: {30, 60, 20, 50, 40, 10} (так как мы делали выше).

2. Перепишите вышеприведенный код сортировки методом выбора в C++ для сортировки в порядке убывания (от наибольшего числа к наименьшему). Хоть это может показаться сложным на первый взгляд, но на самом деле это очень просто.

3. Это задание уже немного сложнее.

Еще одним простым методом сортировки элементов является «сортировка пузырьком». Пузырьковая сортировка работает, сравнивая смежные пары элементов и меняя их местами, если удовлетворяются определенные критерии. И таким образом элементы «скачут пузырьком» до конца массива. Хотя есть несколько способов оптимизировать сортировку пузырьком, в этом задании мы будем придерживаться неоптимизированной версии, так как она проще.

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

A) Сравнивается элемент массива 0 с элементом массива 1. Если элемент 0 больше, то меняем его местами с элементом 1.

B) Теперь выполняем то же самое для элементов 1 и 2 и каждой последующей пары элементов, пока не дойдем до конца массива. Итого получим отсортированный последний элемент массива.

C) Повторяем первые два шага снова, пока массив не будет отсортирован.

Напишите программу, которая отсортирует следующий массив методом пузырька в соответствии с правилами выше:

В конце программы выведите отсортированные элементы массива.

Подсказка: Если мы можем отсортировать только один элемент за одну итерацию, это значит, что нам нужно будет повторить выполнение цикла столько раз, сколько есть чисел в нашем массиве (его длина), дабы гарантировать сортировку всего массива.

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

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

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

Пример вывода вашей программы:

Early termination on iteration 8
1 2 3 4 5 6 7 8 9

Ответы

Ответ 1

30 60 20 50 40 10
10 60 20 50 40 30
10 20 60 50 40 30
10 20 30 50 40 60
10 20 30 40 50 60
10 20 30 40 50 60 (самозамена)
10 20 30 40 50 60 (самозамена)

Ответ 2

Просто измените:

на

Также smallestIndex следует переименовать в largestIndex .

Ответ 3

Ответ 4

Оценить статью:

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (6 оценок, среднее: 4,83 из 5)
Загрузка...
Поделиться в:
Подписаться на обновления:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *