Введение в сортировку в C ++
Имея коллекцию элементов на заказ, сортировка помогает упорядочить элементы в записи на основе отношения порядка. Рассмотрим файловую запись, которая содержит много информации, для доступа к списку из записи необходимо иметь ключевое поле для указания текущего местоположения элемента. Например, рассмотрим список имен в базе данных, он может быть отсортирован по алфавиту. Сортировка занимает важное место в области компьютеров и технологий. Давайте посмотрим больше в этой статье.
Что такое сортировка в C ++?
Сортировка - это основная концепция, используемая программистом или исследователем для сортировки необходимых входных данных. Порядок сложности задается 0 (N * log (N)). Сортировка ввода облегчает решение многих задач, таких как поиск, максимальный и минимальный элемент. Хотя сортировка упорядочивает данные в последовательности, эффективность процесса очень важна, что основано на двух критериях: - Время и память, необходимые для выполнения сортировки по заданным данным. Время измеряется путем подсчета сравнений используемых ключей. Есть много алгоритмов, доступных для сортировки. В общем, сортировка в C ++ различается на два типа:
- Внутренняя сортировка
- Внешняя сортировка
Синтаксис и пример
Синтаксис:
C ++ использует встроенную функцию sort () для своих алгоритмов, чтобы сортировать контейнеры, такие как векторы, массивы.
Сортировка (массив, массив + размер);
Примеры:
#include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
)#include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
)#include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
)
Выход:
Как это работает?
Для начала возьмем Быструю сортировку, которая считается важным методом среди различных типов сортировки. Базовая сортировка массива основана на использовании быстрой сортировки. Существуют различные способы реализации сортировки, цель каждого из этих методов аналогична сравнению двух элементов и замене их временной переменной. В этой статье мы обсудим наиболее важную сортировку, используемую для реализации. Ниже приведены:
- Пузырьковая сортировка
- Сортировка вставки
- Быстрая сортировка
- Выбор сортировки
Есть Merge Sort, radix sort, sort ленты, которые мы можем обсудить позже. Сначала мы пойдем с Bubble.
1. Пузырьковая сортировка
Bubble sort - один из самых простых методов сортировки, который мы можем использовать для приложений. В этом методе последовательные перестановки делаются через записи, которые будут отсортированы. На каждом этапе он сравнивает ключ с данными и обменивается элементами, если не в нужном порядке. Сортировка выполняется со смежными элементами в то время, когда только один элемент помещается в отсортированное место после перестановки.
Пример: рассмотрим несортированный массив A () = (6, 2, 4, 7, 1)
| 6 | 2 | 4 | 7 | 1 |
| А (0) | А (1) | А (2) | А (3) | А (4) |
Шаг 1: Сравнивая A (0)> A (1), если условие истинно, поменяйте местами элемент (6> 2) true, поместите 2 в A (0). Аналогично, все шаги выполняются одинаково, пока массив не станет отсортированным.
Теперь массив A () = (2, 6, 4, 7, 1)
Шаг 2: 6 сравнивается с 4. Поскольку 6 больше 4. Следовательно, 6 и 4 меняются местами.
Теперь массив A () = (2, 4, 6, 7, 1)
Шаг 3: Элемент 6 сравнивается с 7. Поскольку 6 <2 и элементы расположены в порядке возрастания, элементы не меняются местами.
Сортированный массив A () = (2, 4, 6, 7, 1).
Продолжайте процесс, пока массив не будет отсортирован.
2. Вставка сортировки
В этом методе мы начинаем со второго элемента данных, предполагая, что первый элемент уже отсортирован, и сравнение выполняется со вторым элементом, и шаг продолжается с другим последующим элементом. В массиве из N элементов необходимо иметь N-1 проходов, чтобы иметь отсортированный элемент.
Рассмотрим массив A () = (8, 3, 6, 1)
| 8 | 3 | 6 | 1 |
Шаг 1: Первый элемент ищет самый большой элемент в массиве для замены. Если он больше, он остается прежним и переходит ко второму элементу, здесь 8 больше, чем все, обмен не производится.
| 8 | 3 | 6 | 1 |
Шаг 2: Обмен со вторым элементом
| 3 | 8 | 6 | 1 |
Шаг 3: Обмен с третьим элементом
| 3 | 6 | 8 | 1 |
Шаг 4: Обмен с четвертым элементом
| 1 | 3 | 6 | 8 |
3. Быстрая сортировка
Этот метод следует алгоритму «разделяй и властвуй» и считается очень эффективным, а также более быстрым для огромных массивов. Они разделены на три подраздела: левый, правый и средний. Средний элемент имеет единственное значение, и он называется осью. Механизм работает следующим образом: элемент в левом сегменте не должен иметь ключ больше, чем средний элемент, а элемент no справа имеет ключ, который меньше ключа среднего элемента. Теперь давайте начнем с иллюстрации процесса сортировки. Quicksort использует рекурсивную концепцию при сортировке под-части. Массив делится на подчасти, опять же левый и правый сегменты делятся путем завоевания. Здесь, в этом примере, учитывая, что последний элемент имеет поворот, а первый элемент считается низким. Рассмотрим элемент массива
| 49 | 22 | 11 | 16 | 56 | 30 |
Взятие самого правого элемента имеет элемент поворота = 30
| 16 | 22 | 11 | 30 | 56 | 49 |
Элемент больше, чем шарнир, располагается слева, меньше справа.
| 16 | 22 | 11 | 56 | 49 |
Указатель находится на оси и разделен вокруг точки.
| 11 | 22 | 16 | 56 | 49 |
Подразделы сортируются индивидуально.
| 11 | 16 | 22 | 30 | 49 | 56 |
Наконец, мы получили отсортированный массив.
4. Выбор сортировки
Эта методика также называется биржевой сортировкой, которая выполняет поиск и сортировку с двумя операциями. Реализация принимает прямую сортировку выбора, как определено ниже. Здесь требуется идентифицировать наименьший элемент, присутствующий в массиве, и этот элемент сортируется в первой i-й позиции. Далее идентифицируется второй наименьший элемент, и он сортируется во второй позиции. Сортировка выбора выходит из цикла, когда несортированная часть становится пустой. Временная сложность задается как O (n 2 ).
Рассмотрим следующий массив:
| 63 | 26 | 13 | 23 | 12 |
1. Найдите самый маленький элемент и поместите его в начале, и он поменялся местами.
| 12 | 26 | 13 | 23 | 63 |
2. Второй элемент a (1) идентифицируется, сравнивается с минимальным элементом и размещает его во второй позиции, аналогично, проход продолжается.
| 12 | 13 | 26 | 23 | 64 |
Окончательный отсортированный вывод
| 12 | 13 | 23 | 26 | 64 |
Вывод
В заключение, эта статья сфокусирована на сортировке понятий и их рабочих механизмах. Все эти методы сортировки используют концепции параллельной обработки. Сортировка формирует основной строительный блок в алгоритмах структурирования для решения проблем данных в реальном мире путем сортировки набора значений в соответствии с требованиями.
Рекомендуемые статьи
Это руководство по сортировке в C ++. Здесь мы обсуждаем Введение и Синтаксис с примерами, а также Как это работает. Вы также можете просмотреть наши другие предлагаемые статьи, чтобы узнать больше -
- Сортировка в таблице
- Итератор в C ++
- Функции массива в C
- Сортировка кучи в C
- Как сортировка выполняется в PHP?
- Сортировка кучи в Python
- Итератор в Java
- Лучшие 11 функций и преимуществ C ++
- Итератор в Python | Преимущества и примеры Python