16 (1106253)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 161СортировкаПостановка задачиСортировка – это упорядочение наборов однотипных данных,для которых определено отношение линейного порядка(например, <) по возрастанию или по убыванию.Здесь будут рассматриваться целочисленные данные иотношение порядка "<".В стандартную библиотеку stdlib входит функция qsort:void qsort (void *buf, size_t num, size_t size,int(*compare)(const void *, const void *));Функция qsort сортирует (по возрастанию) массив с указателемbuf, используя алгоритм быстрой сортировки Ч.Э.Р. Хоара,который считается одним из лучших алгоритмов сортировкиобщего назначения.Параметр num задает количество элементов массива buf,параметр size – размер (в байтах) элемента массива buf.Параметр int(*compare)(const void *, constvoid *)задает правило сравнения элементов массива num.2СортировкаФункция, указатель на которую передается в qsort в качествеаргумента, соответствующего параметруint(*compare)(const void *, const void *), должнаиметь описание:int имя функции (const void *arg1, const void*arg2)и возвращать:целое < 0, если arg1 < arg2,целое = 0, если arg1 = arg2целое > 0, если arg1 > arg23Сложность алгоритмовРазмер входа: числовая величина, характеризующаяколичество входных данных (например – длина битовой записичисел- параметров алгоритма)Сложность в наихудшем случае: функция размера входа,отражающая максимум затрат на выполнение алгоритма дляданного размеравременнАя сложностьпространственная сложность (затраты памяти)часто оценивают не все затраты, а только самые“дорогие” операцииСложность в среднем: функция размера входа,отражающая средние затраты на выполнение алгоритма длявхода данного размера (учет вероятностей входа)Асимптотические оценки сложности: О-нотация (оценкасверху), точная O-оценка, Θ-оценка.Подробности: С.А.

Абрамов. Лекции о сложности алгоритмов.М.: МЦНМО, 20094СортировкаПростейший алгоритм сортировки: сведение сортировки кзадаче нахождения максимального (минимального) из n чисел.Нахождение максимума n чисел (n сравнений):Числа содержатся в массиве int a[n];max = a[0];for (i = 1; i < n; i++)if (a[i] > max)max = a[i];Алгоритм сортировки: находим максимальное из n чисел,получаем последний элемент отсортированного массива (nсравнений);находим максимальное из n – 1 оставшихся чисел, получаемпредпоследний элемент отсортированного массива (еще n – 1сравнений); и так далее.Общее количество сравнений: 1 + 2 + … + n-1 + n = n(n - 1)/2.Сложность алгоритма O(n2).5СортировкаКлассификация алгоритмов сортировкиРазличают внешнюю и внутреннюю сортировку.Рассматривается только внутренняя сортировка:сортируемый массив находится в основной памяти компьютера.Внешняя сортировка применяется к записям на внешнихфайлах.3 общих метода внутренней сортировки:(1)сортировка обменами: рассматриваются соседниеэлементы сортируемого массива и при необходимостименяются местами;(2)сортировка выборкой: идея описанана предыдущем слайде(3)сортировка вставками: сначала сортируются дваэлемента массива, потом выбирается третий элемент ивставляется в нужную позицию относительно первых6двух и т.д.СортировкаСортировка обменами (пузырьком)Общее количество сравнений (действий): n(n - 1)/2, так каквнешний цикл выполняется (n - 1) раз, а внутренний – в среднемn/2 раза.void bubble_sort (int *a, int n) {int i, j, tmp;for (j = 1; j < n; ++j)for (i = n - 1; i >= j; --i) {if (a[i - 1] > a[i]) {tmp = a[i - 1];a[i - 1] = a[i];a[i] = tmp;}}}7СортировкаСортировка вставкамиКоличество сравнений зависит от степени перемешанностимассива a.

Если массив a уже отсортирован, количествосравнений равно n - 1. Если массив a отсортирован в обратномпорядке (наихудший случай), количество сравнений имеетпорядок n2.void insert_sort (int *a, int n) {int i, j, tmp;for (j = 1; j < n; ++j) {tmp = a[j];for (i = j - 1; i >= 0 && tmp < a[i]; i--)a[i + 1] = a[i];a[i + 1] = tmp;}}8СортировкаОценка сложности алгоритмов сортировкиСкорость сортировки определяется количеством сравнений иколичеством обменов (обмены занимают больше времени).Эти показатели интересны для худшего и лучшего случаев,а также интересно их среднее значение.Кроме скорости оценивается «естественность» алгоритмасортировки:естественным считается алгоритм, который на ужеотсортированном массиве работает минимальное время, а на неотсортированном работает тем дольше, чем больше степень егонеупорядоченности.Важным показателем является и объем дополнительной памятидля хранения промежуточных данных алгоритма.Для рекурсивных алгоритмов расход памяти связан снеобходимостью дублировать стек, в котором расположенынекоторые промежуточные данные.9СортировкаОценка сложности алгоритмов сортировки.Теорема.

Для любого алгоритма S внутренней сортировкисравнением массива из n элементов количество сравненийCS ≥ O(n⋅log2(n))Доказательство.Для любого алгоритма S внутреннейсортировки сравнением массива из n элементовколичество сравненийCS ≥ log2(n!).(1)(a)Алгоритм S можно представить в виде двоичногодерева сравнений.Так как любая перестановка индексоврассматриваемого массива может быть ответом валгоритме, она должна быть приписана хотя быодному листу дерева сравнений.Таким образом, дерево сравнений будетиметь не менее n! листьев.10СортировкаОценка сложности алгоритмов сортировки.Теорема. Для любого алгоритма S внутренней сортировкисравнением массива из n элементов количество сравненийCS ≥ O(n⋅log2(n))Доказательство.Для любого алгоритма S внутреннейсортировки сравнением массива из n элементовколичество сравненийCS ≥ log2(n!).(1)(б)(*)Для высоты hm двоичного дерева с m листьямиимеет место оценка:hm ≥ log2m.Любое двоичное дерево высоты h можно достроить дополного двоичного дерева высоты h, а у полногодвоичного дерева высоты h 2h листьев.Применив полученную оценку к деревусравнений, получим оценку (*)11СортировкаОценка сложности алгоритмов сортировки.Теорема.

Для любого алгоритма S внутренней сортировкисравнением массива из n элементов количество сравненийCS ≥O(n⋅log2(n))Доказательство.(2)К log2(n!) применим формулу Стирлингаn!= 2πn ⋅ n n e − n eϑ ( n )1| ϑ (n) |≤12n(**)Логарифмируя (**), получаем1log(n! ) = log(2πn ) + n ⋅ log(n ) − n + ϑ (n )2log(n! ) ≥ O (n ⋅ log(n ))12Быстрая сортировкаQuickSort – рекурсивная Си-функция следующего вида:/* Быстрая сортировка.

Предполагается, что left<right */static void QuickSort (int *a, int left, int right) {/* comp – компаранд, i, j – значения индексов */int comp, tmp, i, j;i = left; j = right;comp = a[(left + right)/2]; //можно a[left] или a[right]/* построение Partition – цикл do-while */do {while (a[i] < comp && i < right)i++;while (comp < a[j] && j > left)j--;if (i <= j) {tmp = a[i];a[i] = a[j];a[j] = tmp;i++, j--;}} while (i <= j);...}13Быстрая сортировкаQuickSort – рекурсивная Си-функция следующего вида:static void QuickSort (int *a, int left, int right) {.../* продолжение сортировки, если не все отсортировано */if (left < j)QuickSort (a, left, j);if (i < right)QuickSort (a, i, right);}Программа быстрой сортировки.void qsort (int *a, int n) {QuickSort (a, 0, n - 1);}Нужно, чтобы значение компаранда было таким, чтобы он попалв середину результирующей последовательности.

Мы пытаемсяугадать, какой из элементов массива имеет такое значение. Чем14лучше мы угадаем, тем быстрее выполнится алгоритмБыстрая сортировкаПокажем, что цикл do-while действительно строит нужное намразбиение массива a[].(1)В процессе работы цикла индексы i и j не выходят запределы отрезка [left, right], так как в циклах whileвыполняются соответствующие проверки.(2)В момент окончания работы циклаdo-while j ≤ right,так как части разбиения не могут быть пустыми: хотя быодин элемент массива a[] (в крайнем случае a[right])содержится в правой части разбиения.(3)Аналогично, в момент окончания работы циклаdo-while i ≥ left.(4)В момент окончания работы цикла do-while любойэлемент подмассива a[left..j] не больше любогоэлемента подмассива a[i..right], что очевидно.15Быстрая сортировкаРабота цикла do-while на примере: 5 3 2 6 4 1 3 7.Пусть в качестве первого компаранда выбран первыйэлемент массива – 5 (a[left]).Во время первого прохода цикла do-while послевыполнения обоих циклов while получим:(5) 3 2 6 4 1 {3} 7;(в круглых скобках элемент с индексом i,в фигурных – элемент с индексом j).Поскольку i < j, элементы, выделенные скобками,нужно поменять местами (оператор if):3 (3) 2 6 4 {1} 5 7;В результате второго прохода цикла do-while получим:до обмена 3 3 2 (6) 4 {1} 5 7;после обмена 3 3 2 1 ({4}) 6 5 7;Третий проход лишь увеличивает i.Теперь массив a состоит из двух подмассивов3 3 2 1 4 и 6 5 7причем i = 5, j = 4.и нужно рекурсивно применить метод к этим16подмассивам.Быстрая сортировкаПри выборе компаранда можно брать первый элемент, значениекоторого больше значения следующего элемента.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций