Сортировки

Крайне часто в задачах нужно отсортировать массив, но как это сделать? Существует много разных алгоритмов. Давайте поговорим про некоторые алгоритмы и их время выполнения.

Сначала проговорим о самых простых алгоритмах, у которых время выполнения равна O(n²). Такие алгоритмы эффективны только для небольших массивов.

Навигация по странице:
1. Сортировка пузырьком
2. Сортировка выбором
3. Быстрая сортировка
4. Лексикографическая
сортировка строк
5. Сортировка структуры

Сортировка пузырьком

Алгоритм основан на поэтапном сравнении двух соседних элементов массива. Если нам нужно отсортировать массив по неубыванию, то при каждом прохождении внешнего цикла максимальный из оставшихся элементов будет смещаться в конец массива, то есть "сплывать" как пузырёк.
Пример работы алгоритма:

Давайте посмотрим на алгоритм:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int main() {
	int n, i, j, r, A[100];
	scanf("%i", &n);
	for (i = 0; i < n; i++) {
		scanf("%i", &A[i]);
	}
	for (i = 0; i < n - 1; i++) {
		for (j = 0; j < n - i - 1; j++) {
			if (A[j] > A[j + 1]) {
				r = A[j];
				A[j] = A[j + 1];
				A[j + 1] = r;
			}
		}
	}
	for (i = 0; i < n; i++) {
		printf("%i ", A[i]);
	}
return 0;
}

Так как последние элементы по ходу выполнения уже будут отсортированы, то их не нужно проверять в следующие разы, поэтому внутренний цикл до n - i - 1.

Чтобы отсортировать по невозрастанию, нужно в строчке 12 поменять знак больше(>) на меньше(<). Теперь минимальные элементы будут смещаться в конец массива.

Сортировка выбором

Основная суть: берем первый элемент и сравниваем с наименьшим элементом из оставшейся части, если первый элемент больше, то меняем местами эти элементы. Потом берем второй элемент и также сравниваем с наименьшим элементом из оставшейся части и т.д.
Пример работы алгоритма:

Красный цвет - минимальный элемент на данной итерации цикла, синий цвет - просматриваемый элемент, желтый цвет - отсортированная часть массива.
Давайте посмотрим на алгоритм:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int main() {
	int n, i, j, r, min, index, A[100];
	scanf("%i", &n);
	for (i = 0; i < n; i++) {
		scanf("%i", &A[i]);
	}
	for (i = 0; i < n - 1; i++) {
		min = A[i];
		for (j = i + 1; j < n; j++) {
			if (A[j] < min) {
				min = A[j];
				index = j;
			}
		}
		if (min < A[i]) {
			r = A[i];
			A[i] = A[index];
			A[index] = r;
		}
	}
	for (i = 0; i < n; i++) {
		printf("%i ", A[i]);
	}
	return 0;
}

Быстрая сортировка

Само название говорит о быстроте этой сортировки, действительно, эта сортировка является одной из самых быстрых сортировок. В языке Си есть функция данной сортировки под названием qsort(). Эта функция находится в библиотеке stdlib.h.

Параметры функции qsort():
1. Указатель на первый элемент массива;
2. Количество сортируемых элементов;
3. Размер одного элемента массива в байтах;
4. Название функции, которую будет вызывать qsort() для сравнения элементов.

Вот так выглядит функция qsort() для массива A из n целых элементов:

qsort(A, n, sizeof(int), sort);

Функция qsort() передает функции sort указатили на два элемента, которые нужно сравнить. Функция sort возвращает 1, если x1 > x2, 0, если x1 = x2, -1, если x1 < x2.

Вот так выглядит функция sort:

int sort(const void* x1, const void* x2) {
	return *(int*)x1 - *(int*)x2;
}

Чтобы отсортировать массив по невозрастанию, нужно поменять элементы местами:
return *(int*)x2 - *(int*)x1;.

Примеры

Сортировка массива целых чисел по неубыванию:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
 
int sort(const void* x1, const void* x2) {
	return *(int*)x1 - *(int*)x2;
}
 
int main() {
	int n, i, A[100];
	scanf("%i", &n);
	for (i = 0; i < n; i++) {
		scanf("%i", &A[i]);
	}
	qsort(A, n, sizeof(int), sort);
	for (i = 0; i < n; i++) {
		printf("%i ", A[i]);
	}
	return 0;
}

Лексикографическая сортировка строк

Даны n строк до 20 символов в каждой. Пример сортировки по неубыванию строк на Си:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
int sort(const void* x1, const void* x2) {
	return strcmp(*(char**)x1, *(char**)x2);
}
 
int main() {
	int n, i;
	char* str[10];
	scanf("%i", &n);
	getchar();
	for (i = 0; i < n; i++) {
		str[i] = malloc(20*sizeof(char));
		gets(str[i]);
	}
	qsort(str, n, sizeof(char*), sort);
	for (i = 0; i < n; i++) {
		printf("%s\n", str[i]);
	}
	return 0;
}

Если нам нужно сортировать еще и по длине строк, то изменим функцию sort:

int sort(const void* x1, const void* x2) {
	if (strlen(*(char**)x1) > strlen(*(char**)x2)) {
		return 1;
	}
	if (strlen(*(char**)x1) < strlen(*(char**)x2)) {
		return -1;
	}
	return strcmp(*(char**)x1, *(char**)x2);
}

Сортировка структуры

Структура удобный инструмент для выполнения задач. Пусть у нас будет структура p, которая хранит имя и возраст человека:

struct p {  
	char name[10];
	int age;
};

Часто в задачах нужно сортировать структуру по какому-то параметру.
Во-первых, для этого передаем функции sort всю структуру:

qsort(A, n, sizeof(struct p), sort);

Во-вторых, изменяем функцию sort:

int sort(const void* x1, const void* x2) {
	struct p a = *(struct p*)x1;
	struct p b = *(struct p*)x2;
	return a.age - b.age;
}

В данном примере мы сортируем по неубыванию возраст людей. Полный код программы:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
struct p {  
	char name[10];
	int age;
};
 
int sort(const void* x1, const void* x2) {
	struct p a = *(struct p*)x1;
	struct p b = *(struct p*)x2;
	return a.age - b.age;
}
 
int main() {
	int n, i;
	struct p A[100];
	scanf("%i", &n);
	for (i = 0; i < n; i++) {
		scanf("%s%i", &A[i].name, &A[i].age);
	}
	qsort(A, n, sizeof(struct p), sort);
	for (i = 0; i < n; i++) {
		printf("%s %i\n", A[i].name, A[i].age);
	}
	return 0;
}