Язык Си в примерах/Сортировка: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Поставил теги <source>
Нет описания правки
Строка 12: Строка 12:
int n, i;
int n, i;
int a[N];
int a[N];
// считываем количество чисел n
scanf("%d", &n);
scanf("%d", &n);

for(i = 0 ; i < n; i++) { //Считывание n чисел
// считываем n чисел
for(i = 0 ; i < n; i++) {
scanf("%d", &a[i]);
scanf("%d", &a[i]);
}
}
for(i = 0 ; i < n-1 ; i++) { // n раз
for(i = 0 ; i < n-1 ; i++) {
for(j = 0 ; j < n - i -1 ; j++) { // Сравниваем два соседних элемента.
// сравниваем два соседних элемента.
if(a[j] > a[j+1]) { // Если они идут в неправильном порядке, то
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; // меняем их местами.
// меняем их местами.
int tmp = a[j]; a[j] = a[j+1] ; a[j+1] = tmp;
}
}
}
}

Версия от 06:41, 18 июля 2007

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


  1. Компиляция программ
  2. Простейшая программа «Hello World»
  3. Учимся складывать
  4. Максимум
  5. Таблица умножения
  6. ASCII-коды символов
  7. Верхний регистр
  8. Скобочки
  9. Факториал
  10. Степень числа
  11. Треугольник Паскаля
  12. Корень уравнения
  13. Система счисления
  14. Сортировка
  15. Библиотека complex
  16. Сортировка на основе qsort
  17. RPN-калькулятор
  18. RPN-калькулятор на Bison
  19. Простая грамматика
  20. Задача «Расчёт сопротивления схемы»
  21. Простая реализация конечного автомата
  22. Использование аргументов командной строки
  23. Чтение и печать без использования stdio
  24. Декодирование звукозаписи в формате ADX
  25. Другие примеры

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

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

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

 #include<stdio.h>
 #define N 1000
 int main() {
    int n, i;
    int a[N];
    // считываем количество чисел n
    scanf("%d", &n);

    // считываем n чисел
    for(i = 0 ; i < n; i++) { 
        scanf("%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 );

Это функция, описанная в стандартной библиотеке w:ru: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:

1, если a > b
0, если a == b
-1, если 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;
    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 &ndash если они совпадают, и -1 – если первая меньше второй.