Сортировка
Сортировка — это процесс переупорядочивания набора данных в определённом порядке, и она является одной из самых фундаментальных и наиболее глубоко изученных алгоритмических задач в обработке данных.
Семейство алгоритмов сортировки
Простые сортировки (O(n²))
Пузырьковая сортировка, сортировка выбором и сортировка вставками просты в реализации и подходят для небольших объёмов данных или для учебного понимания.
Продвинутые сортировки (O(n log n))
Быстрая сортировка, сортировка слиянием и пирамидальная сортировка наиболее широко используются в инженерии. Сортировка Шелла — это улучшение сортировки вставками.
Примеры
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* Пузырьковая сортировка — O(n²), устойчивая
На каждом проходе наибольший элемент «всплывает» в конец */
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; /* Оптимизация: досрочное завершение */
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = 1;
}
}
if (!swapped) break; /* Уже отсортировано, завершить досрочно */
}
}
/* Функция разбиения Quicksort — O(n log n) в среднем, неустойчивая
Выберите опорный элемент; элементы меньше опорного идут влево, больше — вправо */
int partition(int arr[], int low, int high) {
int pivot = arr[high]; /* Выбрать последний элемент в качестве опорного */
int i = low - 1; /* i указывает на конец области, элементы которой меньше pivot */
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); /* Поместить pivot в правильную позицию */
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); /* Индекс разделения */
quickSort(arr, low, pi - 1); /* Рекурсивно отсортировать левую половину */
quickSort(arr, pi + 1, high); /* Рекурсивно отсортировать правую половину */
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int n1 = 7;
bubbleSort(arr1, n1);
printf("Сортировка пузырьком: "); printArray(arr1, n1);
/* Вывод: 11 12 22 25 34 64 90 */
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr2, 0, 6);
printf("Быстрая сортировка: "); printArray(arr2, 7);
/* Вывод: 11 12 22 25 34 64 90 */
return 0;
}
Иллюстрация концепции «разделяй и властвуй»
Быстрая сортировка (разбиение)
Выбор опорного элемента
Меньше опорного → левая сторона, больше → правая сторона
Рекурсивно отсортировать левый и правый подмассивы
Неустойчивая | На месте | Наиболее часто используется
Сортировка слиянием (Merge)
Рекурсивно делить пополам до наименьшей единицы
Слить две упорядоченные подпоследовательности
Требует дополнительный массив O(n)
Устойчивая | Требует дополнительной памяти | Внешняя сортировка
Пирамидальная сортировка (Heapify)
Построение max-кучи O(n)
Переместить вершину кучи (максимум) в конец
Восстановить кучу O(log n)
Неустойчивая | На месте O(1) | Оптимальная по памяти
Полное сравнение алгоритмов сортировки
| Алгоритм | Лучший | Среднее | Худший | Память | Стабильность |
|---|---|---|---|---|---|
| Пузырьковая сортировка | O(n) | O(n²) | O(n²) | O(1) | Устойчивая |
| Сортировка выбором | O(n²) | O(n²) | O(n²) | O(1) | Неустойчивая |
| Сортировка вставками | O(n) | O(n²) | O(n²) | O(1) | Устойчивая |
| Быстрая сортировка | O(n log n) | O(n log n) | O(n²) | O(log n) | Неустойчивая |
| Сортировка слиянием | O(n log n) | O(n log n) | O(n log n) | O(n) | Устойчивая |
| Пирамидальная сортировка | O(n log n) | O(n log n) | O(n log n) | O(1) | Неустойчивая |
| Сортировка Шелла | O(n log n) | O(n^1.3) | O(n²) | O(1) | Неустойчивая |
Другие расширенияПрактический совет по выбору: для общих сценариев первый выбор — быстрая сортировка; выбирайте сортировку слиянием, когда нужна устойчивость; выбирайте пирамидальную сортировку при крайне ограниченной памяти; выбирайте сортировку вставками для небольших или почти отсортированных данных.