Язык Си в примерах/Сортировка

Язык Си в примерах

Задача «сортировки» (упорядочения) — одна из первых интересных и сложных задач теории алгоритмов. Общие принципы освещает статья «Алгоритмы сортировки», здесь же мы рассматриваем способы упорядочения посредством языка Си.

Метод «пузырька»

Один из простейших алгоритмов решения — метод «пузырька».

 #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; 
           }
        }
    }
 }

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

Задача: Докажите, что достаточно $n-1$ пробега, чтобы элементы массива упорядочились.

Решив эту задачу, вы докажете, что метод «пузырька» решает задачу сортировки.

Функция `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)^[1].

В то же время в качестве четвертого элемента функция qsort хотела бы иметь функцию типа

int cmp(const void*, const void*);

В языке Си можно осуществлять приведение типов являющихся типами функции. В данном примере тип

int (*)(const char*, const char*); // функция, получающая два элемента типа 'const char *' и возвращающая элемент типа 'int'

приводится к типу

int (*)(const void*, const void*); // функция, получающая два элемента типа 'const void *' и возвращающая элемент типа 'int'

Примечания

^ Функция strcmp в соответствии с описанием, выдаваемым командой man 3 strcmp, осуществляет сравнение двух строк и определяет, какая из двух строк идёт первой в алфавитном порядке (сравнивает две строки в лексикографическом порядке), а именно: она возвращает значение больше нуля, если первая строка "больше" второй (идёт после второй в алфавитном порядке), 0 – если они совпадают, и значение меньше нуля– если первая строка "меньше" второй.