Язык Си в примерах/Сортировка
Шаблон:Содержание «Язык Си в примерах»
Задача «сортировки» (упорядочения) — одна из первых интересных и сложных задач теории алгоритмов. Общие принципы освещает статья «Алгоритмы сортировки», здесь же мы рассматриваем способы упорядочения посредством языка Си.
Метод «пузырька»
Один из простейших алгоритмов решения — метод «пузырька».
#include <stdio.h>
int main() {
int n, i, j;
scanf_s("%d", &n);
int a[n];
// считываем количество чисел n
// формируем массив n чисел
for(i = 0 ; i < n; i++) {
scanf_s("%d", &a[i]);
}
for(i = 0 ; i < n - 1; i++) {
// сравниваем два соседних элемента.
for(j = 0 ; j < n - i - 1 ; j++) {
if(a[j] > a[j+1]) {
// если они идут в неправильном порядке, то
// меняем их местами.
int tmp = a[j];
a[j] = a[j+1] ;
a[j+1] = tmp;
}
}
}
}
Понятно, что после первого «пробега» самый большой элемент массива окажется на последнем месте. После второго пробега мы будем уверены, что второй по величине элемент находится на предпоследнем месте.
Задача: Докажите, что достаточно пробега, чтобы элементы массива упорядочились.
Решив эту задачу, вы докажете, что метод «пузырька» решает задачу сортировки.
Функция qsort из библиотеки stdlib
Два оператора for, в которых происходит сортировка, можно заменить на одну строку:
qsort(a, n, sizeof(int), cmp );
Это функция, описанная в стандартной библиотеке ANSI C и объявлена в заголовочном файле stdlib.h.
Поэтому в начале программы нужно добавить
#include <stdlib.h>
Функцией qsort можно упорядочивать объекты любой природы. По сути, она предназначена упорядочивать множества блоков байтов равной длины.
Второй аргумент функции — это число таких блоков, третий аргумент — длина каждого блока.
Первый аргумент — это адрес, где находится начало первого блока (предполагается, что блоки в памяти расположены друг за другом подряд).
Четвёртый аргумент функции qsort — это имя функции, которая умеет сравнивать два элемента массива. В нашем случае это
int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
В силу указанной универсальности функции сортировки, функция сравнения получает в качества аргумента адреса двух блоков, которые нужно сравнить и возвращает 1, 0 или -1:
- положительное значение, если a > b
- 0, если a == b
- отрицательное значение, если a < b
Поскольку у нас блоки байт -- это целые числа (в 32-битной архитектуре это четырёхбайтовые блоки), то необходимо привести данные указатели типа (const void*) к типу (int *) и осуществляется это с помощью дописывания перед указателем выражения «(const int*)». Затем нужно получить значение переменной типа int, которая лежит по этому адресу. Это делается с помощью дописывания спереди звездочки.
Таким образом, мы получили следующую программу
#include <stdio.h>
#include <stdlib.h>
#define N 1000
int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int main() {
int n, i,j;
int a[N];
scanf("%d", &n);
for(i = 0 ; i < n; i++) { // ЧИТАЕМ ВХОД
scanf("%d", &a[i]);
}
qsort(a, n, sizeof(int), cmp ); // СОРТИРУЕМ
for(i = 0 ; i < n; i++) { // ВЫВОДИМ РЕЗУЛЬТАТ
printf("%d ", a[i]);
}
return 0;
}
Динамическое выделение памяти
Ниже приведена программа, где память под массив выделяется динамически:
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int cmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}
int main() {
int n, i;
int *a;
scanf("%d", &n);
a = (int*) malloc(sizeof(int)*n);
for(i = 0 ; i < n; i++) {
scanf("%d", &a[i]);
}
qsort(a, n, sizeof(int), cmp );
for(i = 0 ; i < n; i++) {
printf("%d ", a[i]);
}
free(a);
return 0;
}
Функция malloc (от англ. memory allocation --- выделение памяти) делает запрос к ядру операционной системы по выделению заданного количества байт. Единственный аргумент этой функции — число байт, которое вам нужно. В качестве результата функция возвращает указатель на начало выделенной памяти. Указатель на начало выделенной памяти &mbsah — это адрес ячейки памяти, начиная с которого идут N байт, которые вы можете использовать под любые свои нужды. Всю память, которая была выделена с помощью функции malloc, нужно освобождать с помощью функции free. Аргумент функции free — это указатель на начало выделенной когда-то памяти.
Программа упорядочения строк в алфавитном порядке
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define N 100
#define M 30
int main(int argc, char* argv[]) {
char a[N][M];
int n, i;
scanf("%d", &n);
for (i=0; i<n; i++)
scanf("%s", &a[i]);
qsort(a, n, sizeof(char[M]), (int (*)(const void *,const void *)) strcmp);
for (i=0; i<n; i++)
printf("%s\n", a[i]);
return 0;
}
Обратите внимание на сложное приведение типов.
Функция strcmp, объявленная в файле string.h имеет следующий прототип:
int strcmp(const char*, const char*);
То есть функция получает два аргумента -- указатели на кусочки памяти, где хранятся элементы типа char, то есть два массива символов, которые не могут быть изменены внутри функции strcmp (запрет на изменение задается с помощью модификатора const)Шаблон:Ref.
В то же время в качестве четвертого элемента функция qsort хотела бы иметь функцию типа
int cmp(const void*, const void*);
В языке Си можно осуществлять приведение типов являющихся типами функции. В данном примере тип
int (*)(const char*, const char*); // функция, получающая два элемента типа 'const char *' и возвращающая элемент типа 'int'
приводится к типу
int (*)(const void*, const void*); // функция, получающая два элемента типа 'const void *' и возвращающая элемент типа 'int'
Примечания
- Шаблон:Note Функция strcmp в соответствии с описанием, выдаваемым командой man 3 strcmp, осуществляет сравнение двух строк и определяет, какая из двух строк идёт первой в алфавитном порядке (сравнивает две строки в лексикографическом порядке), а именно: она возвращает значение больше нуля, если первая строка "больше" второй (идёт после второй в алфавитном порядке), 0 – если они совпадают, и значение меньше нуля– если первая строка "меньше" второй.