Лекция
Привет, сегодня поговорим про сортировка в языке си, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое сортировка в языке си , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.
Сортировка — это упорядочивание набора однотипных данных по возрастанию или убыванию. Сортировка является одной из наиболее приятных для умственного анализа категорией алгоритмов, поскольку процесс сортировки очень хорошо определен. Алгоритмы сортировки были подвергнуты обширному анализу, и способ их работы хорошо понятен. К сожалению, вследствие этой изученности сортировка часто воспринимается как нечто само собой разумеющееся. При необходимости отсортировать данные многие программисты просто вызывают стандартную функцию qsort(), входящую в стандартную библиотеку С. Однако различные подходы к сортировке обладают разными характеристиками. Несмотря на то, что некоторые способы сортировки могут быть в среднем лучше, чем другие, ни один алгоритм не является идеальным для всех случаев. Поэтому широкий набор алгоритмов сортировки — полезное добавление в инструментарий любого программиста.
Будет полезно кратко остановиться на том, почему вызов qsort() не является универсальным решением всех задач сортировки. Во-первых, функцию общего назначения вроде qsort() невозможно применить во всех ситуациях. Например, qsort() сортирует только массивы в памяти. Она не может сортировать данные, хранящиеся в связанных списках. Во-вторых, qsort() - параметризованная функция, благодаря чему она может обрабатывать широкий набор типов данных, но вместе с тем вследствие этого она работает медленнее, чем эквивалентная функция, рассчитанная на какой-то один тип данных. Наконец, как вы увидите, хотя алгоритм быстрой сортировки, примененный в функцииqsort(), очень эффективен в общем случае, он может оказаться не самым лучшим алгоритмом в некоторых конкретных ситуациях.
Существует две общие категории алгоритмов сортировки: алгоритмы, сортирующие объекты с произвольным доступом (например, массивы или дисковые файлы произвольного доступа), и алгоритмы, сортирующие последовательные объекты (например, файлы на дисках и лентах или связанные списки[1]). В данной главе рассматриваются только алгоритмы первой категории, поскольку они наиболее полезны для среднестатистического программиста.
Чаще всего при сортировке данных лишь часть их используется в качестве ключа сортировки. Ключ — это часть информации, определяющая порядок элементов. Таким образом, ключ участвует в сравнениях, но при обмене элементов происходит перемещение всей структуры данных. Например, в списке почтовой рассылки в качестве ключа может использоваться почтовый индекс, но сортируется весь адрес. Для простоты в нижеследующих примерах будет производиться сортировка массивов символов, в которых ключ и данные совпадают. Далее вы увидите, как адаптировать эти методы для сортировки структур данных любого типа.
[1]В зависимости от этого сортировка называется внутренней или внешней.
Существует три общих метода сортировки массивов:
Чтобы понять, как работают эти методы, представьте себе колоду игральных карт. Чтобы отсортировать карты методом обмена[1], разложите их на столе лицом вверх и меняйте местами карты, расположенные не по порядку, пока вся колода не будет упорядочена. В методевыбора разложите карты на столе, выберите карту наименьшей значимости и положите ее в руку. Затем из оставшихся карт снова выберите карту наименьшей значимости и положите ее на ту, которая уже находится у вас в руке. Процесс повторяется до тех пор, пока в руке не окажутся все карты; по окончании процесса колода будет отсортирована. Чтобы отсортировать колоду методом вставки, возьмите все карты в руку. Выкладывайте их по одной на стол, вставляя каждую следующую карту в соответствующую позицию. Когда все карты окажутся на столе, колода будет отсортирована.
[1]Т.е. обменной сортировкой.
Существует много различных алгоритмов сортировки. Все они имеют свои положительные стороны, но общие критерии оценки алгоритма сортировки таковы:
Давайте подробнее рассмотрим эти критерии. Очевидно, что скорость работы любого алгоритма сортировки имеет большое значение. Об этом говорит сайт https://intellect.icu . Скорость сортировки[2] массива непосредственно связана с количеством сравнений и количеством обменов, происходящих во время сортировки, причем обмены занимают больше времени. Сравнение происходит тогда, когда один элемент массива сравнивается с другим;обмен происходит тогда, когда два элемента меняются местами. Время работы одних алгоритмов сортировки растет экспоненциально, а время работы других логарифмически зависит от количества элементов.
Время работы в лучшем и худшем случаях имеет значение, если одна из этих ситуаций будет встречаться довольно часто. Алгоритм сортировки зачастую имеет хорошее среднее время выполнения, но в худшем случае он работает очень медленно.
Поведение алгоритма сортировки называется естественным, если время сортировки минимально для уже упорядоченного списка элементов, увеличивается по мере возрастания степени неупорядоченности списка и максимально, когда элементы списка расположены в обратном порядке. Объем работы алгоритма оценивается количеством производимых сравнений и обменов.
Чтобы понять, почему переупорядочивание элементов с одинаковыми ключами имеет определенное значение, представьте себе базу данных почтовой рассылки, упорядоченную по главному ключу и подключу. Главным ключом является почтовый индекс, а в пределах одного почтового индекса записи упорядочены по фамилии. При добавлении в список нового адреса и пересортировке списка порядок подключей (то есть фамилий внутри почтовых индексов) не должен меняться. Для гарантии, что это не произойдет, алгоритм сортировки не должен обменивать ключи с одинаковым значением[3].
Далее будут представлены характерные для каждой группы алгоритмы сортировка с анализом эффективности. После них будут продемонстрированы более совершенные методы сортировки.
[1]Если в отсортированном массиве элементы с одинаковыми ключами идут в том же порядке, в котором они располагались в исходном массиве, то алгоритм сортировки называется устойчивым, а в противном случае — неустойчивым.
[2]Синонимы: быстродействие, эффективность.
[3]Т.е. должен быть устойчивым.
Один из простейших алгоритмов решения — метод «пузырька».
#include <stdio.h>
#define N 1000
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;
}
}
}
}
Понятно, что после первого «пробега» самый большой элемент массива окажется на последнем месте. После второго пробега мы будем уверены, что второй по величине элемент находится на предпоследнем месте.
Задача: Докажите, что достаточно {\displaystyle n-1}
пробега, чтобы элементы массива упорядочились.
Решив эту задачу, вы докажете, что метод «пузырька» решает задачу сортировки.
Два оператора 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'
На этом все! Теперь вы знаете все про сортировка в языке си, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое сортировка в языке си и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов
Комментарии
Оставить комментарий
Алгоритмы и теория алгоритмов
Термины: Алгоритмы и теория алгоритмов