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

  Юрий  | 

    | 

  Обновл. 4 мая 2019  | 

 42280

 ǀ   25 

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

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

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

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

Не секрет, что есть алгоритмы поиска внутри отсортированных массивов и получше. Используя простой алгоритм, мы можем искать определённый элемент в отсортированном массиве, содержащем 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 поменялись местами.

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


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

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

   Начиная с элемента под индексом 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:

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}

Ответ №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

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

Ответ №2

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

на:

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

Задание №3

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

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

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

   Сравнивается элемент массива под индексом 0 с элементом массива под индексом 1. Если элемент под индексом 0 больше элемента под индексом 1, то значения меняются местами.

   Затем мы перемещаемся к следующей пары значений: элемент под индексом 1 и элемент под индексом 2 и так до тех пор, пока не достигнем конца массива.

   Повторяем шаг №1 и шаг №2 до тех пор, пока весь массив не будет отсортирован.

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

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

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

Ответ №3

Задание №4

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

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

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

Пример результата выполнения вашей программы:

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

Ответ №4


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

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (81 оценок, среднее: 4,62 из 5)
Загрузка...

Комментариев: 25

  1. Аватар Дмитрий:

    Думаю используя do while в этой задаче, облегчим понимания "механизма" обработки:

  2. Аватар Константин:

    Версия задания №4 Владимира для тупых (типа меня — сам я не додумался как выполнить это задание, но произвёл тюннинг для лучшего понимания):

  3. Аватар Владимир:

    Задание №4

  4. Аватар Даяна:

    Как вариант решения 4-го задания:

  5. Аватар Виталий:

    №3

  6. Аватар Игорь:

    Я тут начал баловаться с написанной программой и решил посмотреть, что будет если сравнение чисел выйдет за пределы массива… вместо "length-1" поставил "length+10"… результаты были как нулевые, так и со значениями, а ведь программа их между собой меняла местами и мог быть задет какой-нить системный процесс?

    Это я всё к чему… может ли быть та самая "ошибка на единицу" причиной сбоя в работе компутера, вплоть до "синего экрана смерти"? )))

    1. Аватар Александр:

      Ваша программа запускается в "песочнице" и не имеет доступа к системным ресурсам… поэтому и поломать ничего серьезного не выйдет :). Чаще всего такие недочеты приводят просто к непредсказуемым результатам работы программы… Если повезет — к слету (повезет — так как слет заметить несколько проще, чем понять, что за бред вываливается)

      но в общем случае — да. Результат может быть совершенно непредсказуемым. Лет 25 назад, когда трава была зеленее и динозавры ходили между компами, я, еще будучи школотой, пытался разобраться в динамическом выделении памяти под турбо-паскалем… в общем не только краш системы происходил, но и такие забавности, как перезапись биоса, например 🙂

  7. Аватар vit:

    Добрый день!
    Эти статьи перевод или ваши собственные? Если перевод, то где можно найти английский оригинал?

    1. Юрий Юрий:

      Привет. Адаптированный перевод — http://www.LearnCpp.com.

  8. Аватар Алексей:

    Ответ на задачу №3.

  9. Аватар Дасти:

    Мне кажется для кода под заголовком «Сортировка методом выбора в C++» лучше бы убрать лишние переменные — они только запутывают (строчки 15 и 23).
    Для примера мой код:

    1. Аватар Александр:

      В Вашем варианте больше операций обмена. Это никак не меняет асимптотику алгоритма, но за счет появления коэффициента делает его несколько медленей… можно потестить, но "на вскидку" раза в 2-3 медленней.

      ЗЫ для такой сортировки это не критично — она и так тормознутая дальше некуда, но в других алгоритмах такие мелочи очень важны

      1. Аватар Эльнар:

        Да действительно вводят в заблуждение и неправильно работает.
        пыталься отсортировать по первому столбцу, пропуская 1-ю строку

        POS NE NI CDE CDI SP NC SSC NEIE NIIE
        77 0 0 290 290 0 0 0 0 0
        76 0 0 289 289 0 0 0 290 290
        75 0 0 129 129 0 0 0 289 289
        74 0 0 128 128 0 0 0 129 129
        73 0 0 122 122 0 0 0 128 128
        72 0 0 121 121 0 0 0 122 122
        0 1 1 1 1 1 1 1 1 1
        1 2 2 2 2 7 7 7 2 2
        2 3 3 3 3 8 8 13 3 3
        3 4 4 4 4 13 13 14 4 4
        4 6 6 6 6 14 14 112 6 6
        5 7 7 7 7 16 16 113 7 7
        6 8 8 8 8 18 18 114 8 8
        7 13 13 13 13 19 37 0 13 13
        8 14 14 14 14 20 40 0 14 14
        9 16 16 16 16 21 47 0 16 16

        получил что то вроде этого, 0 не сортировался

        POS NE NI CDE CDI SP NC SSC NEIE NIIE

        1 2 2 2 2 7 7 7 2 2

        2 3 3 3 3 8 8 13 3 3

        3 4 4 4 4 13 13 14 4 4

        4 6 6 6 6 14 14 112 6 6

        5 7 7 7 7 16 16 113 7 7

        6 8 8 8 8 18 18 114 8 8

        77 0 0 290 290 0 0 0 0 0

        76 0 0 289 289 0 0 0 290 290

        75 0 0 129 129 0 0 0 289 289

        74 0 0 128 128 0 0 0 129 129

        73 0 0 122 122 0 0 0 128 128

        72 0 0 121 121 0 0 0 122 122

        0 1 1 1 1 1 1 1 1 1

        7 13 13 13 13 19 37 0 13 13

        8 14 14 14 14 20 40 0 14 14

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

  10. Аватар DeeZee:

  11. Аватар Денис:

    № 3

  12. Аватар Алибек:

    №4

  13. Аватар Алибек:

    №3

  14. Аватар Stepan:

    Юр, привет.

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

    1. Юрий Юрий:

      Привет. Что именно вы имеете в виду под встроенными функциями?

      1. Аватар Stepan:

        ну вот, например, была упомянута функция sort(array1 + x, array2 + y), хотелось бы под ней сразу увидеть описание всех аргументов и их возможные вариации (если только это не предмет отдельной главы)

        1. Юрий Юрий:

          Если вы насчет функции sort, то её описывать — получится отдельная статья. А для использования функции sort вам не обязательно знать все её внутренности.

          Если будет возможность — напишу отдельную статью, но это уже будет гораздо позднее.

        2. Аватар master114:

          тоже задался этим вопросом про аргументы функции и вообще как сортирует sort()
          Гугл мало помог, зато помогла книжка "STL для программистов на С++", скачал, распечатал, теперь под рукой всегда.
          Там прочитал, что sort() сортирует массив в восходящем порядке
          А аргументами ему передаются указатели на первый и последний элемент выборки. То есть можно сортировать как весь массив (в таком случае, как в примере мы даем указатели на первый и последний элемент массива), так и любой диапазон (например с 5 по 10 элемент, соответственно аргументами передаются указатели на 5 и 10 элемент).

  15. Аватар Анатолий:

    Использую Microsoft Visual C++ 2017.
    swap работает без подключения algorithm или utility, как так? Так же для работы srand; и rand; не требуется подключение cstdlib.

    1. Юрий Юрий:

      У меня в Microsoft Visual 2017 тоже всё работает без подключения этих библиотек. Возможно, они уже подключены по умолчанию в этой версии Visual. Но когда у меня были более ранние версии Visual-а, то тогда подключать эти библиотеки нужно было.

    2. Аватар Александр:

      Часто библиотеки подключают друг друга. Если Вы хотите убедиться в том, что std::swap (или другой функции) нет в "чистом" языке, то напишите код типа:

      без подключения заголовочных файлов! Такой код не скомпилируется, так как компилятор не знает о std::swap
      Если подключить <алгоритм>, то все заработает. При этом swap гарантировано лежит не в алгоритме! Сейчас он "по цепочке" подтягивается, скажем, с iostream. При этом, если иострим подключал бы алгоритм, то работали бы и другие функции, но этого не происходит.

      Кстати, иострим подтягивает и <string> и еще кучу вкусного 🙂

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

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