Методы сортировки в C++

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

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

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

Мы всегда храним данные в виде записей. Каждая запись состоит из одного или нескольких полей. Когда каждая запись получает уникальное значение определенного поля, это называется ключевым полем. Например, в классе Roll No может быть уникальным или ключевым полем.

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

Точно так же в телефонном справочнике каждая запись состоит из имени человека, адреса и номера телефона. При этом номер телефона является уникальным или ключевым полем. Мы можем отсортировать данные справочника по этому телефонному полю. В качестве альтернативы мы также можем сортировать данные либо в числовом, либо в алфавитно-цифровом порядке.

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

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

В этой статье мы подробно рассмотрим различные методы сортировки в C++.

Методы сортировки

Язык C++ поддерживает различные методы сортировки, они перечислены ниже:

Пузырьковая сортировка

Пузырьковая сортировка (сортировка простыми обменами) — это простейший метод, при котором мы сравниваем каждый элемент с соседним элементом и меняем местами элементы, если они не в нужном нам порядке. Таким образом, в конце каждой итерации (называемой проходом) самый тяжелый (больший) элемент всплывает в конце списка.

Ниже приведен пример пузырьковой сортировки.

Массив для сортировки:

Массив для сортировки

Проход 1

Проход 2

Проход 3

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

Давайте реализуем метод пузырьковой сортировки в скетче на C++:

Вывод данных:

Список ввода…
10 2 0 43 12
Отсортированный список элементов…
0 2 10 12 43

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

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

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

Читать также:  Константы в С++

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

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

Проход 1 в сортировке выбором

Проход 2 в сортировке выбором

Проход 3 в сортировке выбором

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

Далее давайте реализуем сортировку выбором с помощью C++:

Вывод данных:

Введите список элементов для сортировки
12 45 8 15 33
Отсортированный список элементов
8 12 15 33 45

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

Сортировка вставками

Сортировка вставками — это метод, при котором мы начинаем сортировать со второго элемента списка. Мы сравниваем второй элемент с его предыдущим (первым) элементом и помещаем его на свое место. На следующем проходе для каждого элемента мы сравниваем его со всеми предыдущими элементами и вставляем этот элемент на свое место.

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

Техника будет ясна, если вы поймете следующие схемы.

Массив для сортировки выглядит следующим образом:

Сортировка вставками

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

Проходы в сортировке вставками

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

Давайте реализуем технику сортировки вставками на C++:

Вывод данных:

Список ввода
12 4 3 1 15
Отсортированный список
1 3 4 12 15

Приведенный выше вывод данных показывает полный отсортированный массив с использованием сортировки вставками.

Быстрая сортировка

Быстрая сортировка — наиболее эффективный алгоритм, который можно использовать для сортировки данных. Этот метод использует стратегию «разделяй и властвуй», в которой задача делится на несколько подзадач и после решения этих подзадач по отдельности объединяются в полный отсортированный список.

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

Быстрая сортировка

Как показано на приведенной выше схеме, в технике быстрой сортировки мы делим массив около опорного элемента таким образом, что все элементы, меньше опорного элемента, находятся слева от него, а элементы, превышающие опорный элемент, — справа. Затем мы берем эти два массива независимо друг от друга и сортируем их, а затем объединяем их, чтобы получить результирующий отсортированный массив.

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

Читать также:  Язык Java в сравнении с другими языками

Давайте реализуем технику быстрой сортировки с помощью C++:

Вывод данных:

Входной массив
12 23 3 43 51
Массив, отсортированный с помощью быстрой сортировки
3 12 23 43 51

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

Сортировка слиянием

Это еще одна техника, использующая стратегию «Разделяй и властвуй». В этой технике мы сначала делим список на равные половины. Затем мы выполняем метод сортировки слиянием в этих списках независимо, чтобы оба списка были отсортированы. Наконец, мы объединяем оба списка, чтобы получить полный отсортированный список.

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

Давайте посмотрим на приведенную схему техники сортировки слиянием:

Сортировка слиянием

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

Далее давайте реализуем сортировку слиянием с использованием языка C++:

Вывод данных:

Введите количество элементов для сортировки: 5
Введите 5 элементов для сортировки: 10 21 47 3 59
Отсортированный массив:
3 10 21 47 59

Сортировка Шелла (ракуши)

Сортировка Шелла является расширением метода сортировки вставками. В сортировке вставками мы имеем дело только со следующим элементом, тогда как в сортировке Шелла мы предоставляем приращение, с помощью которого мы создаем меньшие списки из родительского списка. Элементы в подсписках не обязательно должны быть смежными, скорее они обычно отделены друг от друга по ‘gap_value’.

Сортировка Шелла выполняется быстрее, чем сортировка вставками, и требует меньше действий:

Сортировка Шелла

Если мы обеспечим зазор, то у нас будут следующие подсписки с каждым элементом, который находится на расстоянии 3 элементов друг от друга.

Затем мы сортируем эти три подсписка:

Три подсписка

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

Сортировка ракуши

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

Читать также:  Стандартная библиотека шаблонов (STL): краткое введение

Ниже приведена реализация сортировки Шелла в C++:

Вывод данных:

Массив для сортировки:
45 23 53 43 18
Массив после сортировки Шелла:
18 23 43 45 53

Таким образом, сортировка Шелла действует как огромное улучшение по сравнению с сортировкой вставками и даже не требует половины шагов для сортировки массива.

Пирамидальная сортировка (сортировка кучей)

Пирамидальная сортировка — это метод, в котором структура данных кучи (min-heap или max-heap) используется для сортировки списка. Сначала мы создаем кучу из несортированного списка, а также используем кучу для сортировки массива.

Пирамидальная сортировка эффективна, но не так быстра, как сортировка слиянием:

Пирамидальная сортировка

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

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

Теперь давайте реализуем сортировку кучей с помощью C++:

Вывод данных:

Входной массив:
4 17 3 12 9
Отсортированный массив:
3 4 9 12 17

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

Итог

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

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

Методы сортировки позволяют нам сортировать наши структуры данных в определенном порядке и располагать элементы в порядке возрастания или убывания. Мы рассказали подробно вам о таких методах сортировки, как сортировка пузырьком, сортировка выбором, сортировка вставками, быстрая сортировка, сортировка Шелла и сортировка слиянием. Пузырьковая сортировка и сортировка выбором проще в реализации.

В нашей последующей статье мы подробно рассмотрим технику пузырьковой сортировки в C++.

С Уважением, МониторБанк

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