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

Материал из Викиучебника

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

[править] Метод «пузырька»

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

 #include<stdio.h>
 #define N 1000
 int main() {
    int n, i, j;
    int a[N];
    // считываем количество чисел n
    scanf("%d", &n);
 
    // считываем n чисел
    for(i = 0 ; i < n; i++) { 
        scanf("%d", &a[i]);
    }
    for(i = 0 ; i < n ; 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>
 #define N 1000
 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'

[править] Примечания

1. ^  Функция strcmp в соответствии с описанием, выдаваемой командой man 3 strcmp, осуществляет сравнение двух строк

и определяет какая из двух строк идёт первой в алфавитном порядке (стравнивает две строки в лексографическом порядке), а именно, она возвращает 1, если первая строка больше второй (идёт после второй в алфавитном порядке), 0 – если они совпадают, и -1 – если первая меньше второй.