Сортировки - это важный инструмент в программировании на языке C++. Они используются для упорядочивания данных, например, чисел или строк. Существует множество различных алгоритмов сортировки, каждый из которых имеет свои преимущества и недостатки. В этой статье мы рассмотрим некоторые из наиболее распространенных алгоритмов сортировки в C++.
Сортировка пузырьком
Сортировка пузырьком - это один из самых простых алгоритмов сортировки. Он проходит по массиву несколько раз, меняя местами соседние элементы, если они находятся в неправильном порядке. Каждый проход по массиву гарантирует, что самый большой элемент перемещается в конец массива.
Пример кода сортировки пузырьком:
```
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
```
Этот код принимает массив arr размера n и сортирует его методом пузырька.
Сортировка вставками
Сортировка вставками - это алгоритм сортировки, который проходит по массиву и вставляет каждый элемент в правильную позицию относительно уже отсортированных элементов. Каждый новый элемент сравнивается со всеми предыдущими элементами, пока не будет найдено место, куда он может быть вставлен.
Пример кода сортировки вставками:
```
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
```
Этот код принимает массив arr размера n и сортирует его методом вставок.
Быстрая сортировка
Быстрая сортировка - это алгоритм сортировки, который использует стратегию "разделяй и властвуй". Он разбивает массив на две части, выбирает опорный элемент и перемещает все элементы меньше опорного элемента на одну сторону, а все элементы больше опорного элемента - на другую сторону. Затем алгоритм рекурсивно применяется к каждой из двух частей.
Пример кода быстрой сортировки:
```
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
```
Этот код принимает массив arr и его границы low и high и сортирует его методом быстрой сортировки.
В заключение, сортировки - это важный инструмент в программировании на языке C++. Наиболее распространенные алгоритмы сортировки - сортировка пузырьком, сортировка вставками и быстрая сортировка. Каждый из них имеет свои преимущества и недостатки, и выбор алгоритма зависит от конкретной задачи и размера данных, которые нужно отсортировать.
