10.4 – Сортировка массива с помощью сортировки выбором
Случай для сортировки
Сортировка массива – это процесс упорядочивания всех элементов в массиве в определенном порядке. Существует много разных случаев, когда сортировка массива может быть полезна. Например, ваш почтовый клиент обычно отображает электронные письма в порядке времени их получения, поскольку более свежие сообщения обычно считаются более актуальными. Когда вы переходите к списку контактов, имена обычно располагаются в алфавитном порядке, потому что так легче найти имя, которое вы ищете. Оба этих примера включают в себя сортировку данных перед их представлением.
Сортировка массива может сделать поиск в массиве более эффективным не только для людей, но и для компьютеров. Например, рассмотрим случай, когда мы хотим знать, появляется ли имя в списке имен. Чтобы узнать, есть ли имя в списке, нам нужно проверить каждый элемент в массиве. Для массива с большим количеством элементов поиск по всем элементам может быть дорогостоящим.
Однако теперь предположим, что наш массив имен отсортирован по алфавиту. В этом случае нам нужно выполнить поиск только до того момента, когда мы встретим имя, которое в алфавитном порядке больше искомого. На этом этапе, если мы не нашли имя, то мы знаем, что его нет и в остальной части массива, потому что все имена, которые мы не просмотрели в массиве, гарантированно будут в алфавитном порядке больше!
Оказывается, есть даже лучшие алгоритмы поиска в отсортированных массивах. Используя простой алгоритм, мы можем выполнять поиск в отсортированном массиве, содержащем 1000000 элементов, используя всего 20 операций сравнения! Обратной стороной является, конечно, то, что сортировка массива сравнительно дорога, и не стоит часто сортировать массив, чтобы ускорить поиск, если только вы не собираетесь искать в нем много раз.
В некоторых случаях сортировка массива может сделать поиск ненужным. Рассмотрим другой пример, в котором мы хотим найти лучший результат теста. Если массив не отсортирован, мы должны просмотреть каждый элемент в массиве, чтобы найти максимальный результат теста. Если список отсортирован, лучший результат теста будет на первой или последней позиции (в зависимости от того, в каком порядке мы отсортировали, по возрастанию или по убыванию), поэтому нам вообще не нужно искать!
Как работает сортировка
Сортировка обычно выполняется путем многократного сравнения пар элементов массива и их обмена местами, если они соответствуют некоторым предопределенным критериям. Порядок, в котором сравниваются эти элементы, различается в зависимости от используемого алгоритма сортировки. Критерии зависят от того, как будет отсортирован список (например, в порядке возрастания или убывания).
Чтобы поменять местами два элемента, мы можем использовать функцию std::swap() из стандартной библиотеки C++, которая определена в заголовке utility.
#include <iostream>
#include <utility>
int main()
{
int x{ 2 };
int y{ 4 };
std::cout << "Before swap: x = " << x << ", y = " << y << '\n';
std::swap(x, y); // меняем местами значения x и y
std::cout << "After swap: x = " << x << ", y = " << y << '\n';
}Эта программа печатает:
Before swap: x = 2, y = 4
After swap: x = 4, y = 2Обратите внимание, что после обмена значения x и y поменялись местами!
Сортировка выбором
Существует много способов отсортировать массив. Сортировка выбором, вероятно, является самым простым для понимания алгоритмом, что делает ее хорошим кандидатом для обучения, даже несмотря на то, что это одна из самых медленных сортировок.
Сортировка выбором выполняет следующие шаги для сортировки массива от наименьшего к наибольшему:
- начиная с индекса массива 0, выполнить поиск по всему массиву, чтобы найти наименьшее значение;
- поменять местами наименьшее значение, найденное в массиве, со значением с индексом 0;
- повторите шаги 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:
{ 10, 20, 50, 30, 40 }
Теперь мы можем игнорировать первые два элемента. Ищем наименьший элемент, начиная с индекса 2:
{ 10, 20, 50, 30, 40 }
И меняем его местами с элементом с индексом 2:
{ 10, 20, 30, 50, 40 }
Ищем наименьший элемент, начиная с индекса 3:
{ 10, 20, 30, 50, 40 }
И меняем его местами с элементом с индексом 3:
{ 10, 20, 30, 40, 50 }
Наконец, ищем наименьший элемент, начиная с индекса 4:
{ 10, 20, 30, 40, 50 }
И меняем его местами с элементом с индексом 4 (что ничего не делает):
{ 10, 20, 30, 40, 50 }
Готово!
{ 10, 20, 30, 40, 50 }
Обратите внимание, что последнее сравнение всегда будет с самим собой (что является избыточным), поэтому мы можем фактически остановиться на 1 элементе до конца массива.
Сортировка выбором в C++
Вот как этот алгоритм реализован на C++:
#include <iostream>
#include <iterator>
#include <utility>
int main()
{
int array[]{ 30, 50, 20, 10, 40 };
constexpr int length{ static_cast<int>(std::size(array)) };
// Пройдемся по каждому элементу массива (кроме последнего,
// который уже будет отсортирован к тому моменту, когда мы туда доберемся)
for (int startIndex{ 0 }; startIndex < length - 1; ++startIndex)
{
// smallestIndex - это индекс наименьшего элемента, с которым мы столкнулись в этой итерации
// Начнем с предположения, что наименьший элемент является первым элементом этой итерации
int smallestIndex{ startIndex };
// Затем ищем меньший элемент в остальной части массива
for (int currentIndex{ startIndex + 1 }; currentIndex < length; ++currentIndex)
{
// Если мы нашли элемент, который меньше нашего ранее найденного наименьшего
if (array[currentIndex] < array[smallestIndex])
// тогда отслеживаем его
smallestIndex = currentIndex;
}
// smallestIndex теперь самый маленький элемент в оставшемся массиве
// меняем местами наш начальный элемент самым маленьким элементом
// (это сортирует его в нужное место)
std::swap(array[startIndex], array[smallestIndex]);
}
// Теперь, когда весь массив отсортирован, распечатываем наш отсортированный
// массив в качестве доказательства, что всё работает
for (int index{ 0 }; index < length; ++index)
std::cout << array[index] << ' ';
std::cout << '\n';
return 0;
}Самая запутанная часть этого алгоритма – это цикл внутри другого цикла (вложенный цикл). Внешний цикл (startIndex) перебирает каждый элемент один за другим. Для каждой итерации внешнего цикла внутренний цикл (currentIndex) используется для поиска наименьшего элемента в оставшейся части массиве (начиная с startIndex + 1). smallestIndex отслеживает индекс наименьшего элемента, найденного внутренним циклом. Затем меняются местами значения элементов с индексами smallestIndex и startIndex. Наконец, внешний цикл (startIndex) сдвигается на один элемент, и процесс повторяется.
Подсказка: если у вас возникли проблемы с пониманием того, как работает приведенная выше программа, может быть полезно проработать пример этого случая на листе бумаги. Напишите начальные (несортированные) элементы массива по горизонтали вверху листа. Нарисуйте стрелки, указывающие, на какие элементы указывают индексы startIndex, currentIndex и smallestIndex. Вручную проследите выполнение программы и перерисуйте стрелки по мере изменения индексов. Для каждой итерации внешнего цикла начинайте новую строку, показывающую текущее состояние массива.
Сортировка имен работает по тому же алгоритму. Просто измените тип массива с int на std::string и инициализируйте соответствующими значениями.
std::sort
Поскольку сортировки массивов настолько распространены, стандартная библиотека C++ включает в себя функцию сортировки с именем std::sort. std::sort находится в заголовке <algorithm> и может быть вызвана для массива следующим образом:
#include <algorithm> // для std::sort
#include <iostream>
#include <iterator> // для std::size
int main()
{
int array[]{ 30, 50, 20, 10, 40 };
std::sort(std::begin(array), std::end(array));
for (int i{ 0 }; i < static_cast<int>(std::size(array)); ++i)
std::cout << array[i] << ' ';
std::cout << '\n';
return 0;
}По умолчанию std::sort сортирует в порядке возрастания с использованием оператора < для сравнения пар элементов и их обмена местами при необходимости (так же, как в нашем примере сортировки выбором выше).
Подробнее о std::sort мы поговорим в следующей главе.
Небольшой тест
Вопрос 1
Покажите вручную, как работает сортировка выбором для следующего массива: {30, 60, 20, 50, 40, 10}. Покажите состояние массива после каждой перестановки.
Ответ
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
Перепишите приведенный выше код сортировки выбора для сортировки в порядке убывания (сначала наибольшие числа). Хотя это может показаться сложным, на самом деле это удивительно просто.
Ответ
Просто измените:
if (array[currentIndex] < array[smallestIndex])на
if (array[currentIndex] > array[smallestIndex])
smallestIndex, вероятно, также следует переименовать вlargeIndex.#include <iostream> #include <iterator> // для std::size #include <utility> int main() { int array[]{ 30, 50, 20, 10, 40 }; constexpr int length{ static_cast<int>(std::size(array)) };// C++17 // constexpr int length{ sizeof(array) / sizeof(array[0]) }; // если C++17 не поддерживается // Пройдемся по каждому элементу массива, кроме последнего for (int startIndex{ 0 }; startIndex < length - 1; ++startIndex) { // largestIndex - это индекс самого большого элемента, // с которым мы столкнулись на данный момент int largestIndex{ startIndex }; // Поиск по всем элементам, начиная с startIndex + 1 for (int currentIndex{ startIndex + 1 }; currentIndex < length; ++currentIndex) { // Если текущий элемент больше, чем самый большой найденный ранее if (array[currentIndex] > array[largestIndex]) // Это новое наибольшее число для этой итерации largestIndex = currentIndex; } // Меняем местами наш начальный элемент с самым большим элементом std::swap(array[startIndex], array[largestIndex]); } // Теперь распечатываем наш отсортированный массив // в качестве доказательства, что всё работает for (int index{ 0 }; index < length; ++index) std::cout << array[index] << ' '; std::cout << '\n'; return 0; }
Вопрос 3
Это будет непросто, так что примите вызов.
Еще один простой алгоритм сортировки называется «пузырьковой». Пузырьковая сортировка работает, сравнивая соседние пары элементов и меняя их местами, если критерии соблюдены, в итоге элементы «пузыряются» к концу массива. Хотя способов оптимизации пузырьковой сортировки существует немало, в этом тесте мы будем придерживаться неоптимизированной версии, потому что она простейшая.
Неоптимизированная пузырьковая сортировка выполняет следующие шаги для сортировки массива от наименьшего к наибольшему:
- Сравнить элемент 0 с элементом 1. Если элемент 0 больше, поменять его местами с элементом 1.
- Теперь сделать то же самое для элементов 1 и 2, а также для каждой последующей пары элементов, пока не дойдем до конца массива. На этом этапе будет отсортирован последний элемент в массиве.
- Повторять первые два шага снова, пока массив не будет отсортирован полностью.
Напишите код, который отсортирует следующий массив в соответствии с приведенными выше правилами:
int array[]{ 6, 3, 2, 9, 7, 1, 5, 4, 8 };И в конце вашей программы распечатайте отсортированные элементы массива.
Подсказка: если мы можем отсортировать по одному элементу за итерацию, это означает, что, чтобы гарантировать сортировку всего массива, нам нужно будет повторять итерации примерно столько раз, сколько чисел в нашем массиве.
Подсказка: сравнивая пары элементов, будьте осторожны с диапазоном вашего массива.
Ответ
#include <iostream> #include <iterator> // для std::size #include <utility> int main() { int array[]{ 6, 3, 2, 9, 7, 1, 5, 4, 8 }; constexpr int length{ static_cast<int>(std::size(array)) }; // C++17 // constexpr int length{ sizeof(array) / sizeof(array[0]) }; // если C++17 не поддерживается // Пройдемся по каждому элементу массива (кроме последнего, который уже // будет отсортирован к тому моменту, когда мы доберемся до него) for (int iteration{ 0 }; iteration < length-1; ++iteration) { // Перебираем все элементы до конца массива - 1 // У последнего элемента нет пары для сравнения for (int currentIndex{ 0 }; currentIndex < length - 1; ++currentIndex) { // Если текущий элемент больше, чем элемент после него, меняем их местами if (array[currentIndex] > array[currentIndex+1]) std::swap(array[currentIndex], array[currentIndex + 1]); } } // Теперь распечатываем наш отсортированный массив // в качестве доказательства, что всё работает for (int index{ 0 }; index < length; ++index) std::cout << array[index] << ' '; std::cout << '\n'; return 0; }
Вопрос 4
Добавьте две оптимизации к алгоритму пузырьковой сортировки, который вы написали в предыдущем вопросе теста:
- Обратите внимание, как с каждой итерацией пузырьковой сортировки наибольшее оставшееся число переносится в конец массива. После первой итерации сортируется последний элемент массива. После второй итерации также сортируется предпоследний элемент массива. И так далее... На каждой итерации нам не нужно повторно проверять элементы, которые, как мы знаем, уже отсортированы. Измените цикл, чтобы повторно не проверять уже отсортированные элементы.
- Если мы проходим всю итерацию без замены, то мы знаем, что массив уже должен быть отсортирован. Реализуйте проверку, чтобы определить, производились ли в этой итерации какие-либо обмены местами, и если нет, прервите цикл раньше. Если цикл был прерван досрочно, выведите, на какой итерации сортировка завершилась раньше.
Ваш вывод должен соответствовать следующему:
Early termination on iteration 6
1 2 3 4 5 6 7 8 9Ответ
#include <iostream> #include <iterator> // для std::size #include <utility> int main() { int array[]{ 6, 3, 2, 9, 7, 1, 5, 4, 8 }; constexpr int length{ static_cast<int>(std::size(array)) }; // C++17 // constexpr int length{ sizeof(array) / sizeof(array[0]) }; // если C++17 не поддерживается // Пройдемся по каждому элементу массива, кроме последнего for (int iteration{ 0 }; iteration < length-1; ++iteration) { // Учет того, что последний элемент уже отсортирован при каждой последующей итерации // чтобы наш массив "заканчивался" на один элемент раньше int endOfArrayIndex{ length - iteration }; // Отслеживаем, поменялись ли какие-либо элементы местами на этой итерации bool swapped{ false }; // Перебираем все элементы до конца массива - 1 // У последнего элемента нет пары для сравнения for (int currentIndex{ 0 }; currentIndex < endOfArrayIndex - 1; ++currentIndex) { // Если текущий элемент больше, чем элемент после него if (array[currentIndex] > array[currentIndex + 1]) { // Меняем их местами std::swap(array[currentIndex], array[currentIndex + 1]); swapped = true; } } // Если мы не поменяли местами какие-либо элементы на этой итерации, // значит, мы закончили раньше if (!swapped) { // Итерации отсчитываются от 0, но счетчик итераций отсчитывает от 1. // Поэтому добавьте сюда 1 для коррекции. std::cout << "Early termination on iteration: " << iteration+1 << '\n'; break; } } // Теперь распечатываем наш отсортированный массив // в качестве доказательства, что всё работает for (int index{ 0 }; index < length; ++index) std::cout << array[index] << ' '; std::cout << '\n'; return 0; }