Методы сортировки

Теоретические сложности  рассмотренных методов сортировки:

	Tmax	Tmid	Tmin	Omax
Подсчетом	n2			n
Включением	n2		n	1
Шелла	n2	n1,25	n	1
Извлечением	n2			1
Древесная	n*log(n)			1
Пузырьковая	n2		n	1
Быстрая	n2	n*log(n)		log(n)
Слиянием	n*log(n)			n
Распределением	n			n

Эти таблицы позволяют  сделать ряд выводов.

1. На небольших наборах данных целесообразнее использовать сортировку включением, так как из всех методов, имеющих очень простую программную реализацию, этот на практике оказывается самым быстрым и при размерностях<~3000 дает вполне приемлемую для большинства случаев скорость работы. Еще одно преимущество этого метода заключается в том, что он использует полную или частичную упорядоченность входных данных и на упорядоченных данных работает быстрее, а на практике данные, как правило, уже имеют хотя бы частичный порядок.
2. Алгоритм пузырьковой сортировки, причем в той его модификации, которая не использует частичный порядок данных исходного массива, хотя и часто используется, но имеет плохие показатели даже среди простых методов с квадратичной сложностью.
3. Сортировка Шелла оказывается лишь красивым теоретическим методом, потому что на практике использовать его нецелесообразно: он сложен в реализации, но не дает такой скорости, какую дают сравнимые с ним по сложности программной реализации методы.
4. При сортировке больших массивов исходных данных лучше использовать быструю сортировку.
5. Если же добавляется требование гарантировать приемлемое время работы метода (как вы помните, быстрая сортировка в худшем случае имеет сложность T(N²), хотя вероятность такого случая очень мала), то надо применять либо древесную сортировку, либо сортировку слиянием. Как видно из таблиц, сортировка слиянием работает быстрее, но следует помнить, что она требует дополнительную память размером порядка N.
6. В тех же случаях, когда мы можем себе позволить использовать дополнительную память размером порядка n, имеет смысл воспользоваться сортировкой распределением.

3. Контрольные  вопросы

1. Что такое сортировка? Чем отличаются внешняя и внутренняя сортировка?
2. Что такое практическая и теоретическая сложности? Можно ли из практической сложности вывести теоретическую? Можно ли из теоретической сложности вывести практическую?
3. Что такое максимальная, средняя и минимальная сложности?
4. Что означает T(1)?
5. Общее в методах сортировки включением (сортировки включением и метода Шелла)?
6. Доказать, что метод Шелла действительно сортирует массив.
7. Общее в методах сортировки извлечением (сортировки извлечением и древесная)?
8. Описать способ хранения двоичного дерева, используемый в древесной сортировке.
9. Что такое регулярная вершина дерева? регулярное поддерево?
10. Доказать, что древесная сортировка действительно сортирует массив.
11. Почему нельзя сделать так, чтобы быстрая сортировка давала гарантированную сложность T(n*log(n))? (Подсказка: причина в алгоритме выбора среднего элемента)
12. Как мы можем гарантировать пространственную сложность O(log(n)) при реализации метода быстрой сортировки?
13. Доказать, что сортировка слиянием действительно сортирует массив.
14. Доказать, что сортировка распределением действительно сортирует массив.

4. Методические  указания.

Перед выполнением индивидуального  задания ознакомиться с понятиями  временной и пространственной сложности, методами сортировки, их сравнительным  анализом.

При выполнении индивидуального  задания придерживаться следующей  последовательности действий:

1. изучить словесную постановку задачи;
2. выбрать метод сортировки, который лучше всего подходит для решения поставленной задачи;
3. разработать программу, решающую поставленную задачу;
4. оттестировать и отладить программу;
5. написать и представить к защите отчет по работе.

5. Содержание отчета

1. Титульный лист.
2. Словесная постановка задачи.
3. Алгоритм решения задачи в текстуальном виде.
4. Обоснование правильности работы алгоритма и правильности выбора метода сортировки исходя из постановки задачи.
5. Листинг программы.
6. Ответы на контрольные вопросы по согласованию с преподавателем.

6. Варианты индивидуальных  заданий

Сортировка имеет множество  практических применений: прямых, когда  прямо ставится задача отсортировать  данные; и косвенных, когда при  решении какой-либо задачи требуется  промежуточная сортировка данных. Здесь  будут приведены ряд задач, при  решении которых удобно использовать сортировку.

Во всех задачах надо обязательно  показать, почему Ваш алгоритм обеспечивает заданную временную сложность.

Задача 1. Найти количество различных чисел среди элементов данного массива. Обеспечить число действий порядка n*log n.

Указание. Отсортировать числа, а затем посчитать количество различных, просматривая элементы массива по порядку.

Задача 2. Найти k-ое по порядку число среди элементов данного массива. Обеспечить число действий порядка n*log n.

Указание. Отсортировать массив, а затем взять число, хранящееся в элементе массива с индексом k.

Задача 3. Дано n отрезков [A[i], B[i]] на прямой (i=1..n), где A[i] – одномерная координата начала отрезка, а B[i] – конца отрезка.

Найти максимальное k, для  которого существует точка прямой, покрытая k отрезками ("максимальное число слоев"). Обеспечить число  действий - порядка n*log n.

Указание. Упорядочим все левые и правые концы отрезков вместе (при этом левый конец считается меньше правого конца, расположенного в той же точке прямой). Далее двигаемся слева направо, считая число слоев. Встреченный левый конец увеличивает число слоев на 1, правый - уменьшает. Отметим, что примыкающие друг к другу отрезки обрабатываются правильно: сначала идет левый конец (правого отрезка), а затем - правый (левого отрезка).

Задача 4. Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Обеспечить число действий порядка n*log n.

Указание. Упорядочим точки по x-координате, а при равных x-координатах - по y-координате. В таком порядке и можно проводить ломаную.

Задача 5. Та же задача, если ломаная должна быть замкнутой.

Указание. Возьмем самую левую точку (т.е. точку с наименьшей x-координатой) и проведем из нее лучи во все остальные точки. Теперь упорядочим эти лучи, а точки на одном луче поместим в порядке увеличения расстояния от начала луча.

Задача 6. Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Форму выпуклой оболочки примет резиновое колечко, если его натянуть на гвозди, вбитые в точках.) Обеспечить число операций порядка n*log n.

Указание. Упорядочим точки - годится любой из порядков, использованных в двух предыдущих задачах. Затем, рассматривая точки по очереди, будем строить выпуклую оболочку уже рассмотренных точек. (Для хранения выпуклой оболочки полезно использовать дек – смотрите главу «Стеки, очереди, деки»)

Задача 7. Дан массив, состоящий из чисел 0, 1 и 2. Переместить все 0 в начало массива, а 2 – в конец. Обеспечить число действий порядка n.

Указание. Воспользоваться вырожденной сортировкой распределением.

Задача 8. В неупорядоченном массиве А могут быть совпадающие элементы. Из каждой группы одинаковых элементов оставить только один, удалив остальные и «поджав» массив к его началу. Обеспечить число операций порядка n*log n.

Указание. Можно сначала отсортировать массив, а затем произвести его «поджатие» с удалением повторяющихся. При удалении очередного повтора не надо сразу сдвигать весь массив (это может привести к сложности T(n²)) – достаточно, рассматривая массив поэлементно и помня последний рассмотренный элемент, либо пропускать очередной, либо приписывать его к уже просмотренной части.

Задача 9. Турнирная таблица соревнований представлена квадратной матрицей A, каждый элемент которой a_ij есть число голов, забитых i-ой командой в ворота j-ой команды. По диагонали расположить место каждой команды (по числу побед за вычетом числа поражений; в случае равенства – по разности забитых и пропущенных голов).

Задача 10. В целочисленном массиве найти наибольшее число одинаковых элементов.

Указание. Удобно предварительно отсортировать массив.

Задача 11. Отсортировать список по неубыванию. Гарантировать число действий порядка n. Элементы списка могут содержать числа от 1 до 1000000000.

Указание. Воспользоваться сортировкой распределением.