Лекция 11. Сортировка (Электронные лекции)

Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.Лекция 11 Сортировка11.1. Сортировка. Постановка задачи.11.1.1. Сортировка – это упорядочение наборов однотипных данных, для которых определеноотношение линейного порядка (например, <) по возрастанию или по убыванию. Здесьбудут рассматриваться целочисленные данные и отношение порядка "<".11.1.2. В стандартную библиотеку stdlib входит функция qsort:void qsort (void *buf, size_t num, size_t size,int(*compare)());Функция qsort сортирует (по возрастанию) массив с указателем buf, используяалгоритм быстрой сортировки Ч.Э.Р.

Хоара, который считается одним из лучшихалгоритмов сортировки общего назначения. Параметр num задает количествоэлементов массива buf, параметр size – размер (в байтах) каждого элемента массиваbuf.Функция, указатель на которую передается в qsort в качестве аргумента,соответствующего параметру int(*compare)(), должна иметь описание:int имя функции (const void *arg1, const void *arg2)Эта функция должна возвращатьцелое < 0, если arg1 < arg2,целое = 0, если arg1 = arg2,целое > 0, если arg1 > arg2,11.2. Указатель на функцию.11.2.1. Каждая функция располагается в памяти по определенному адресу, который можноприсвоить указателю в качестве его значения.

Адресом функции является ее точкавхода (при вызове функции управление передается именно на эту точку). Указательфункции можно использовать вместо ее имени при вызове этой функции. Указатель«лучше» имени тем, что его можно передавать другим функциям в качестве ихаргумента. Имя функции f()без скобок и аргументов (f) по определению являетсяуказателем на функции f() (аналогия с массивом).11.2.2. Пример. Сравнение двух строк символов, введенных пользователем (функцияcheck()).#include <stdio.h>#include <string.h>void check(char *a, char *b, int (*cmp)(const char*, constchar*));int main() {char s1[80], s2[80];/*объявление указателя на функцию */int (*p)(const char *, const char *);/* указателю p присваивается адрес функции strcmp() *//* из стандартной библиотеки string */p = strcmp;printf("Введите две строки \n");gets(s1);gets(s2);check(s1, s2, p);return 0;}(с) Кафедра системного программирования ф-та ВМК МГУ, 20101Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.void check(char *a, char *b, int (*cmp)(const char*, constchar*)){printf("Проверка на совпадение \n");if(!(*cmp)(a, b))) printf("Равны");;else printf("Не равны");}11.2.3.

Пояснения к примеру.(1) Объявление int (*p)(const char *, const char *); сообщаеткомпилятору, что p – указатель на функцию, имеющую два параметра типа constchar * и возвращающую значение типа int. Скобки вокруг *p нужны, так какоперация * имеет более низкий приоритет, чем (). Если написать int *p(...)получится, что объявлен не указатель функции, а функция p, которая возвращаетуказатель на целое.(2) (*cmp)(a, b) эквивалентно cmp(a, b) (имя функции имеет те же свойства,что и имя массива – 11.1.3) и при создании языка Си вариант cmp(a, b) оченьнравился его авторам, но потом выяснилось, что использование этого варианта вомногих случаях мешает правильно понять программу при ее чтении.(3) У функции check три параметра: два указателя на тип char и указатель нафункцию cmp. Указатели p и cmp имеют одинаковый формат, что позволяетиспользовать p в качестве аргумента, соответствующего параметру p.(4) В данном случае использование указателя функции позволяет менять программусравнения и тем самым получается более общий алгоритм.

Например, для сравнениястрок можно использовать не библиотечную функцию strcmp(), а следующуюфункцию compvalues(), которая, используя функцию atoi() из стандартнойбиблиотеки stdlib, сравнивает числа, записанные во входных строках.int compvalues(const char *a, const char *b) {if(atoi(a) == atoi(b)) return 0;else return 1;}11.3. Алгоритмы сортировки.11.3.1. Почему qsort считается лучшим алгоритмом сортировки общего назначения? Дляответа на этот вопрос рассмотрим проблему сортировки более подробно.11.3.2.

Даже если считать алгоритм Хоара лучшим алгоритмом сортировки общегоназначения библиотечной функции qsort недостаточно, чтобы покрыть всепотребности.(1) qsort сортирует только массивы (не может сортировать, например, связанныесписки).(2) qsort, будучи ориентированной на широкий набор типов обрабатываемыхданных, работает медленнее, чем специализированная функция сортировки (например,за счет вызова функции для сравнения).11.3.3.

В некоторых ситуациях алгоритм быстрой сортировки работает плохо (это будетпоказано ниже).11.3.4. Простейший алгоритм сортировки: сведение сортировки к задаче нахождениямаксимального (минимального) из n чисел.11.3.4.1. Нахождение максимума n чисел (n сравнений):Числа содержатся в массиве int a[n]max = a[0];(с) Кафедра системного программирования ф-та ВМК МГУ, 20102Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.for(i = 1; i < n; i++) if(a[i] > max) max = a[i];11.3.4.2. Алгоритм сортировки: находим максимальное из n чисел, получаемпоследний элемент отсортированного массива (n сравнений); находиммаксимальное из n – 1 оставшихся чисел, получаем предпоследний элементотсортированного массива (еще n – 1 сравнений); и так далее.11.3.4.3.

Общее количество сравнений: 1 + 2 + … + n-1 + n = n(n - 1). Сложностьалгоритма O(n2). Скорость выполнения алгоритма обратно пропорциональнаего сложности.11.3.5. Классификация алгоритмов сортировки.11.3.5.1. Различают внешнюю и внутреннюю сортировку. Здесь рассматриваетсятолько внутренняя сортировка, когда сортируемый массив находится восновной памяти компьютера. Внешняя сортировка применяется к записямвнешних файлов.11.3.5.2. Существует три общих метода внутренней сортировки:(1) сортировка обменами: рассматриваются соседние элементы сортируемогомассива и при необходимости меняются местами;(2) сортировка выборкой: см. 11.3.4.2.(3) сортировка вставками: сначала сортируются два элемента массива, потомвыбирается третий элемент и вставляется в нужную позициюотносительно первых двух и т.д.11.3.6.

Оценка сложности алгоритмов сортировки.11.3.6.1. Скорость сортировки определяется количеством сравнений и количествомобменов (обмены занимают больше времени). Эти показатели интересны дляхудшего и лучшего случаев, а также интересно их среднее значение.11.3.6.2. Кроме скорости оценивается «естественность» алгоритма сортировки:естественным считается алгоритм, который на уже отсортированном массивеработает минимальное время, а на не отсортированном работает тем дольше,чем больше степень его неупорядоченности.11.3.6.3.

Важным показателем является и объем дополнительной памяти для храненияпромежуточных данных алгоритма. Для рекурсивных алгоритмов расходпамяти связан с необходимостью дублировать стек, в котором расположенынекоторые промежуточные данные.11.3.6.4. Докажем, что для любого алгоритма S внутренней сортировки массива из nэлементов количество сравнений CS ≥ n⋅log2(n)Можно доказать, что для любого алгоритма S внутренней сортировкимассива из n элементов количество сравнений CS ≥ log2(n!). В самом деле,алгоритм S можно представить в виде двоичного дерева сравнений.

Так каклюбая перестановка индексов рассматриваемого массива может быть ответомв алгоритме, она должна быть приписана хотя бы одному листу деревасравнений. Таким образом, дерево сравнений будет иметь не менее n! листьев.Нетрудно также показать, что для высоты hm двоичного дерева с m листьямиимеет место оценка: hm ≥ log2m.

Это следует из того, что любое двоичноедерево высоты h можно достроить до полного двоичного дерева высоты h, а вполного двоичного дерева высоты h 2h листьев. Следовательно, m ≤ 2 hm откудаhm ≥  log 2 m . Применив полученную оценку к дереву сравнений, получим CS≥ log2(n!). Для оценки log2(n!) воспользуемся формулой Стирлингаn!≈ 2π n ⋅ n n e − n , что даст требуемую оценку.(с) Кафедра системного программирования ф-та ВМК МГУ, 20103Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год.11.3.7.