Сортировка посредством выбора

При сортировке посредством выбора^[1] из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n - 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. Эти обмены продолжаются до двух последних элементов. Например, если применить метод выбора к массиву dcab, каждый проход будет выглядеть так, как показано ниже:

Начало d c a b Проход 1 a c d b Проход 2 a b d c Проход 3 a b c d

Сортировка Хоара

В методе Хоара первоначально выделяют базовый элемент, относительно которого ключи с большим весом перебрасываются вправо, а с меньшим влево. Базовый элемент сравнивается с противоположным элементом.

В качестве базового элемента очень удобно брать крайние элементы.

Давайте рассмотрим пример:

Дано множество{9,6,3,4,10,8,2,7}

Берем 9 в качестве базового элемента. Сравниваем 9 с противоположностоящим элементом, в данном случае это 7. 7 меньше, чем 9, следовательно элементы меняются местами.

{ 7,6,3,4,10,8,2, 9 }

Далее начинаем последовательно сравнивать элементы с 9, и менять их местами в зависимости от сравнения.

{7, 6,3,4,10,8,2, 9 }{7,6, 3,4,10,8,2, 9 }{7,6,3, 4,10,8,2, 9 }{7,6,3,4, 9,8,2, 10 } - 9 и 10 меняем местами.{7,6,3,4, 8, 9,2,10} - 9 и 8 меняем местами.{7,6,3,4,8, 2, 9,10} - 2 и 9 меняем местами.

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

{7,6,3,4,8,2}{10}

Далее по уже отработанному алгоритму сортируются эти подмножества. Подмножество из одного элемента естественно можно не сортировать. Выбираем в первом подмножестве базовый элемент 7.

{7,6,3,4,8,2} { 2,6,3,4,8, 7 } - меняем местами 2 и 7.{2, 6,3,4,8, 7 }{2,6, 3,4,8, 7 }{2,6,3, 4,8, 7 }{2,6,3,4, 7, 8 }- меняем местами 7 и 8

Получили снова два подмножества.

{2,6,3,4}{8}

А дальше все происходит аналогично...

Сортировка Шелла

В 1959 году Дональд Шелл опубликовал усовершенствованный алгоритм сортировки вставками, который впоследствии получил его имя. Идея данного метода заключается в сравнение разделенных на группы элементов некоторой последовательности.

Сначала, сравниваются элементы находящиеся друг от друга на расстоянии d (первое d обычно равно n/2, где n — количество всех элементов). Постепенно расстояние между элементами уменьшается, и на d=1 сортировка происходит последний раз.

Ниже Вы можете наблюдать реализацию сортировки Шелла на примере последовательности чисел: 5, 3, 8, 0, 7, 4, 9, 1, 6, 2. Здесь в качестве промежуточных значений взяты значения 5, 2, 1. Для удобной ориентации, элементы одной группы выделены одинаковым цветом.

 

Так элементы постепенно становятся на свои позиции, и на последнем шаге (d=1) число перестановок будет совсем невелико.

 

14. Модули и библиотеки стандартных программ в универсальных языках программирования. Основные виды библиотечных функций по назначению (на примере языка программирования Паскаль или Си++).

Стандартная библиотека языка программирования — набор модулей, классов, объектов, констант, глобальных переменных, шаблонов, макросов, функций и процедур, доступных для вызова из любой программы, написанной на этом языке и присутствующих во всех реализациях языка.

Состав

В зависимости от возможностей языка, стандартная библиотека может содержать:

· процедуры и функции

· макросы

· глобальные переменные

· классы

· шаблоны

Обычно стандартная библиотека содержит основные алгоритмы и структуры данных, необходимые для:

· работы с динамической памятью;

· файловыми операциями ввода-вывода;

· операциями ввода-вывода данных на терминал;

· конвертацией данных между типами;

· функции для работы со структурами данных: строками, массивами, списками и т. п.;

· математические операции;

· функции для работы с сетью;

· функции для обеспечения обработки исключений и ошибок в программе;

· функции для поддержки многопоточности.

Бьёрн Страуструп выдвинул следующие 11 принципиальных требований к средствам, предлагаемым стандартной библиотекой:

1. Востребованность — быть важными доступными для всех пользователей языка.

2. Используемость — прямо или косвенно использоваться всеми программистами для решения всех задач, связанных с целями библиотеки.

3. Эффективность — для большинства применений библиотечная реализация должна быть не хуже реализации тех же механизмов «вручную».

4. Независимость от алгоритмов — предоставлять возможность задавать алгоритмы в качестве параметров. Например, стандартная функция сортировки должна давать возможность определить любой алгоритм сравнения элементов.

5. Математическая примитивность — каждая компонента должна предоставлять одну определённую функцию либо группу функций, используемых только совместно.

6. Удобство, эффективность и безопасность — по крайней мере, в большинстве типичных вариантов применения.

7. Завершённость — «Стандартная библиотека может оставить множество функций другим библиотекам, но если уж она взялась за какую-то задачу, то должна обеспечить достаточную функциональность, чтобы отдельным пользователям и разработчикам не приходилось заменять её средства».

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

9. Типобезопасность — безопасность с точки зрения типов по умолчанию.

10. Поддержка общепринятых стилей программирования.

11. Расширяемость — способность единообразно работать со встроенными типами данных и с типами, определяемыми пользователем.

Реализация в синтаксисе языка

В некоторых языках функции ввода/вывода являются частью синтаксиса самого языка (например, Basic, Pascal, Python) и не могут быть воспроизведены как самостоятельные функции (процедуры). С одной стороны, это позволяет создавать более гибкий синтаксис для операторов вывода (например, оператор вывода на экран writeln в Pascal существенно проще по синтаксису чем функция printf в стандартной библиотеке языка Си), с другой стороны, это усложняет синтаксис языка и затрудняет использование компилятора языка для создания программ не использующих эти возможности (например, в встраиваемых компьютерах).