Язык Си в примерах/Сортировка: различия между версиями
Greck (обсуждение | вклад) |
Поставил теги <source> |
||
Строка 6: | Строка 6: | ||
Один из простейших алгоритмов решения — «метод пузырька». |
Один из простейших алгоритмов решения — «метод пузырька». |
||
<source lang="c"> |
|||
#include<stdio.h> |
|||
#define N 1000 |
#define N 1000 |
||
int main() { |
int main() { |
||
Строка 22: | Строка 23: | ||
} |
} |
||
} |
} |
||
} |
} |
||
</source> |
|||
Понятно, что после первого «пробега» самый большой элемент массива окажется на последнем месте |
Понятно, что после первого «пробега» самый большой элемент массива окажется на последнем месте |
||
Строка 39: | Строка 41: | ||
<code>qsort(a, n, sizeof(int), cmp );</code> |
<code>qsort(a, n, sizeof(int), cmp );</code> |
||
Это функция, описанная в стандартной библиотеке [[w: |
Это функция, описанная в стандартной библиотеке [[w:ru:ANSI C]] и объявлена в заголовочном файле <tt>stdlib.h</tt>. |
||
Поэтому в начале программы нужно добавить |
Поэтому в начале программы нужно добавить |
||
Строка 52: | Строка 54: | ||
два элемента массива. В нашем случае это |
два элемента массива. В нашем случае это |
||
<source lang="c"> |
|||
int cmp(const void *a, const void *b) { |
|||
return *(int*)a - *(int*)b; |
return *(int*)a - *(int*)b; |
||
} |
} |
||
</source> |
|||
В силу указанной универсальности функции сортировки, функция сравнения получает в качества аргумента адреса двух блоков, которые нужно сравнить и возвращает 1, 0 или -1: |
В силу указанной универсальности функции сортировки, функция сравнения получает в качества аргумента адреса двух блоков, которые нужно сравнить и возвращает 1, 0 или -1: |
||
Строка 68: | Строка 72: | ||
Таким образом, мы получили следующую программу |
Таким образом, мы получили следующую программу |
||
<source lang="c"> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
#include <stdlib.h> |
||
#define N 1000 |
#define N 1000 |
||
Строка 86: | Строка 91: | ||
} |
} |
||
return 0; |
return 0; |
||
} |
} |
||
</source> |
|||
== Динамическое выделение памяти == |
== Динамическое выделение памяти == |
||
Строка 92: | Строка 98: | ||
Ниже приведена программа, где память под массив выделяется динамически: |
Ниже приведена программа, где память под массив выделяется динамически: |
||
<source lang="c"> |
|||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Строка 114: | Строка 121: | ||
return 0; |
return 0; |
||
} |
} |
||
</source> |
|||
Функция <tt>malloc<tt> (от англ. ''memory allocation'' --- ''выделение памяти'') делает запрос к ядру операционной системе по выделению заданного количества байт. Единственный аргумент этой функции — число байт, которое вам нужно. В качестве результата функция возвращает указатель на начало выделенной памяти. Указатель на начало выделенной памяти &mbsah это адрес ячеки памяти, начиная с которого идут N байт, которые вы можете использовать под любые свои нужды. Всю память, которая была выделена с помощью функции <tt>malloc<tt>, нужно освобождать с помощью функции <tt>free</tt>. Аргумент функции <tt>free</tt> — это указатель на начало выделенной когда-то памяти. |
Функция <tt>malloc<tt> (от англ. ''memory allocation'' --- ''выделение памяти'') делает запрос к ядру операционной системе по выделению заданного количества байт. Единственный аргумент этой функции — число байт, которое вам нужно. В качестве результата функция возвращает указатель на начало выделенной памяти. Указатель на начало выделенной памяти &mbsah это адрес ячеки памяти, начиная с которого идут N байт, которые вы можете использовать под любые свои нужды. Всю память, которая была выделена с помощью функции <tt>malloc<tt>, нужно освобождать с помощью функции <tt>free</tt>. Аргумент функции <tt>free</tt> — это указатель на начало выделенной когда-то памяти. |
||
== Программа упорядочения строк в алфавитном порядке == |
== Программа упорядочения строк в алфавитном порядке == |
||
<source lang="c"> |
|||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <string.h> |
#include <string.h> |
||
Строка 136: | Строка 143: | ||
return 0; |
return 0; |
||
} |
} |
||
</source> |
|||
Обратите внимание на сложное приведение типов. |
Обратите внимание на сложное приведение типов. |
Версия от 16:15, 5 июня 2007
- Компиляция программ
- Простейшая программа «Hello World»
- Учимся складывать
- Максимум
- Таблица умножения
- ASCII-коды символов
- Верхний регистр
- Скобочки
- Факториал
- Степень числа
- Треугольник Паскаля
- Корень уравнения
- Система счисления
- Сортировка
- Библиотека complex
- Сортировка на основе qsort
- RPN-калькулятор
- RPN-калькулятор на Bison
- Простая грамматика
- Задача «Расчёт сопротивления схемы»
- Простая реализация конечного автомата
- Использование аргументов командной строки
- Чтение и печать без использования stdio
- Декодирование звукозаписи в формате ADX
- Другие примеры
Задача сортировки (упорядочения) — одна из первых интересных и сложных задач теории алгоритмов. Об общих принципах читайте статью «Алгоритмы сортировки» в журнале «Потенциал», здесь же мы рассматриваем способы упорядочения посредством языка Си.
Метод «пузырька»
Один из простейших алгоритмов решения — «метод пузырька».
#include<stdio.h>
#define N 1000
int main() {
int n, i;
int a[N];
scanf("%d", &n);
for(i = 0 ; i < n; i++) { //Считывание n чисел
scanf("%d", &a[i]);
}
for(i = 0 ; i < n-1 ; i++) { // n раз
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'
Примечания
- ^ Функция strcmp в соответствии с описанием, выдаваемой командой man 3 strcmp, осуществляет сравнение двух строк
и определяет какая из двух строк идёт первой в алфавитном порядке (стравнивает две строки в лексографическом порядке), а именно, она возвращает 1, если первая строка больше первой (идёт после второй в алфавитном порядке), 0 &ndash если они совпадают, и -1 – если первая меньше второй.