Можешь перечислить основные алгоритмы сортировки и объяснить их принципы?

Основные алгоритмы сортировки и их принципы:

1. Пузырьковая сортировка (Bubble Sort) — многократное проходы по массиву, при которых соседние элементы сравниваются и меняются местами, если они в неправильном порядке. Простой, но неэффективный алгоритм.

2. Сортировка выбором (Selection Sort) — на каждом шаге выбирается минимальный (или максимальный) элемент из неотсортированной части и меняется местами с первым элементом этой части.

3. Сортировка вставками (Insertion Sort) — элементы по одному вставляются в уже отсортированную часть массива, сдвигая элементы при необходимости.

4. Быстрая сортировка (Quick Sort) — выбирается опорный элемент (pivot), массив разбивается на части с элементами меньше и больше опорного, затем рекурсивно сортируются эти части.

5. Сортировка слиянием (Merge Sort) — массив рекурсивно делится пополам, затем отсортированные половины сливаются в один отсортированный массив.

6. Пирамидальная сортировка (Heap Sort) — строится куча (heap) из элементов, затем максимальный элемент извлекается и помещается в конец массива, повторяется для оставшихся элементов.

Пример пузырьковой сортировки на 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]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}