Алгоритм сортировки на C
Пузырьковая сортировка
Пузырьковая сортировка (англ.: Bubble Sort) — это простой алгоритм сортировки. Он многократно проходит по списку, который нужно отсортировать, сравнивая по два элемента за раз, и меняет их местами, если они стоят в неправильном порядке (например, от большего к меньшему или первой буквы от A до Z).
Демонстрация процесса:
Пример
#include <stdio.h>
// Объявление функции
void bubble_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Вычислить длину массива
bubble_sort(arr, len); // Вызов функции пузырьковой сортировки
// Вывести отсортированный массив
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Функция пузырьковой сортировки
void bubble_sort(int arr[], int len) {
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
// Поменять местами элементы
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
Сортировка выбором
Сортировка выбором — простой и интуитивно понятный алгоритм сортировки. Принцип его работы следующий. Сначала находим наименьший (или наибольший) элемент в неотсортированной последовательности и помещаем его в начало отсортированной последовательности. Затем продолжаем находить наименьший (или наибольший) элемент среди оставшихся неотсортированных элементов и помещаем его в конец отсортированной последовательности. И так далее, пока все элементы не будут отсортированы.
Демонстрация процесса:
Пример
#include <stdio.h>
// Объявление функции
void selection_sort(int a[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Вычислить длину массива
selection_sort(arr, len); // Вызов функции сортировки выбором
// Вывести отсортированный массив
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Функция сортировки выбором
void selection_sort(int a[], int len) {
for (int i = 0; i < len - 1; i++) {
int min = i; // Записываем позицию минимального значения; первый элемент по умолчанию считается минимальным.
for (int j = i + 1; j < len; j++) {
if (a[j] < a[min]) { // Находим текущий минимум
min = j; // Записываем позицию минимального значения
}
}
// Поменять местами две переменные
if (min != i) {
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}
/*// Пользовательская функция swap
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}*/
Сортировка вставками
Сортировка вставками (англ. Insertion Sort) — простой и интуитивно понятный алгоритм сортировки. Принцип его работы заключается в построении упорядоченной последовательности. Для неотсортированных данных выполняется сканирование отсортированной последовательности от конца к началу, находится подходящая позиция, и элемент вставляется в неё. В реализации сортировка вставками обычно использует сортировку на месте (то есть сортировку, требующую только {\displaystyle O(1)} {\displaystyle O(1)} дополнительного пространства). Поэтому в процессе сканирования от конца к началу необходимо многократно сдвигать отсортированные элементы назад шаг за шагом.
Сдвиг, чтобы освободить место для нового элемента.Демонстрация процесса:
Пример
#include <stdio.h>
// Объявление функции
void insertion_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Вычислить длину массива
insertion_sort(arr, len); // Вызвать функцию сортировки вставками
// Вывести отсортированный массив
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Функция сортировки вставками
void insertion_sort(int arr[], int len) {
for (int i = 1; i < len; i++) {
int temp = arr[i]; // Текущий элемент для вставки
int j = i;
// Переместить элементы, большие чем temp, вправо
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp; // Вставить элемент в правильную позицию
}
}
Сортировка Шелла
Сортировка Шелла, также известная как алгоритм сортировки с уменьшающимся шагом, является более эффективной улучшенной версией сортировки вставками. Сортировка Шелла — неустойчивый алгоритм сортировки.
Сортировка Шелла предлагает улучшения, основанные на следующих двух свойствах сортировки вставками:
- Сортировка вставками очень эффективна при работе с данными, которые почти уже отсортированы, и может достигать эффективности линейной сортировки.
- Но сортировка вставками обычно неэффективна, потому что сортировка вставками может перемещать данные только на одну позицию за раз.
Демонстрация процесса:
Пример
#include <stdio.h>
// Объявление функции
void shell_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Вычислить длину массива
shell_sort(arr, len); // Вызвать функцию сортировки Шелла
// Вывести отсортированный массив
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Функция сортировки Шелла
void shell_sort(int arr[], int len) {
// Вычислить начальный шаг
for (int gap = len / 2; gap > 0; gap /= 2) {
// Выполнить сортировку вставками для каждого шага
for (int i = gap; i < len; i++) {
int temp = arr[i]; // Текущий элемент для вставки
int j = i;
// Переместить элементы больше temp
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp; // Вставить элемент в правильную позицию
}
}
}
Сортировка слиянием
Разделите данные на два сегмента и из этих двух сегментов поочерёдно выбирайте наименьший элемент и перемещайте его в конец нового сегмента данных.
Можно выполнять сверху вниз или снизу вверх.
Демонстрация процесса:
Итеративный метод
#include <stdio.h>
#include <stdlib.h>
// Объявление функции
int min(int x, int y);
void merge_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Вычислить длину массива
merge_sort(arr, len); // Вызвать функцию сортировки слиянием
// Вывести отсортированный массив
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Вернуть минимум из двух чисел
int min(int x, int y) {
return x < y ? x : y;
}
// Функция сортировки слиянием
void merge_sort(int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int));
if (b == NULL) { // Проверить, успешно ли выделена память
fprintf(stderr, "Не удалось выделить память\n");
exit(EXIT_FAILURE);
}
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start;
int mid = min(start + seg, len);
int high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
// Объединить два подмассива
while (start1 < end1 && start2 < end2) {
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
}
while (start1 < end1) {
b[k++] = a[start1++];
}
while (start2 < end2) {
b[k++] = a[start2++];
}
}
// Поменять местами указатели массива
int* temp = a;
a = b;
b = temp;
}
// Если a и arr различаются, скопировать содержимое a обратно в arr
if (a != arr) {
for (int i = 0; i < len; i++) {
b[i] = a[i];
}
b = a;
}
free(b); // освободить память
}
Рекурсивный метод
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Объявление функции
void merge_sort_recursive(int arr[], int reg[], int start, int end);
void merge_sort(int arr[], const int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]); // Вычислить длину массива
merge_sort(arr, len); // Вызвать функцию сортировки слиянием
// Вывести отсортированный массив
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
// Рекурсивно реализовать сортировку слиянием
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int mid = start + (end - start) / 2;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2) {
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 <= end1) {
reg[k++] = arr[start1++];
}
while (start2 <= end2) {
reg[k++] = arr[start2++];
}
// Используйте memcpy для копирования массивов для повышения эффективности
memcpy(arr + start, reg + start, (end - start + 1) * sizeof(int));
}
// Входная функция для сортировки слиянием
void merge_sort(int arr[], const int len) {
int* reg = (int*)malloc(len * sizeof(int));
if (reg == NULL) { // Проверить, успешно ли выделена память
fprintf(stderr, "Не удалось выделить память\n");
exit(EXIT_FAILURE);
}
merge_sort_recursive(arr, reg, 0, len - 1);
free(reg); // освободить память
}
Быстрая сортировка
Случайно выбрать элемент в интервале в качестве опорного, разместить элементы меньше опорного перед опорным, а элементы больше опорного после опорного, затем отсортировать область меньших элементов и область больших элементов отдельно.
Демонстрация процесса:
Итеративный метод
#include <stdio.h>
// Структура Range
typedef struct _Range {
int start, end;
} Range;
// Создать новый диапазон
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
// Поменять местами два целых числа
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
// Функция быстрой сортировки
void quick_sort(int arr[], const int len) {
if (len <= 0)
return; // Избежать ошибки сегментации, когда len отрицательно
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p > 0) {
Range range = r[--p];
if (range.start >= range.end)
continue;
int mid = arr[(range.start + range.end) / 2]; // Выбрать среднюю точку в качестве опорного элемента
int left = range.start, right = range.end;
do {
while (arr[left] < mid) ++left; // Проверить, удовлетворяет ли левая сторона опорного элемента требованиям
while (arr[right] > mid) --right; // Проверить, удовлетворяет ли правая сторона опорного элемента требованиям
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--; // Переместить указатели, чтобы продолжить
}
} while (left <= right);
if (range.start < right) r[p++] = new_Range(range.start, right);
if (range.end > left) r[p++] = new_Range(left, range.end);
}
}
int main() {
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = sizeof(arr) / sizeof(arr[0]); // Вычислить длину массива
quick_sort(arr, len); // Вызвать функцию быстрой сортировки
// Вывести отсортированный массив
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Рекурсивный метод
#include <stdio.h>
// Поменять местами два целых числа
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
// Рекурсивная реализация быстрой сортировки
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (left < right && arr[left] < mid)
left++;
while (left < right && arr[right] >= mid)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
// Входная функция быстрой сортировки
void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
int main() {
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = sizeof(arr) / sizeof(arr[0]); // Вычислить длину массива
quick_sort(arr, len); // Вызвать функцию быстрой сортировки
// Вывести отсортированный массив
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}