Лабораторная работа №1. Реализация алгоритмов сортировки и поиска

Задачи работы

Задачами данной лабораторной работы являются:

1. Закрепление навыков программирования на языке C++, в частности, навыков работы с массивами, указателями и функциями.

2. Контроль освоения студентами теоретического материала – информации об алгоритмах сортировки и поиска.

Задание на лабораторную работу

Разработать программу на языке C++, реализующую алгоритм сортировки или поиска в соответствии с индивидуальным вариантом задания.

Варианты задания:

1. Реализовать сортировку Шелла (описана ниже).

2. Реализовать сортировку шейкером (описана ниже).

3. Реализовать сортировку подсчетом для массива данных типа char [5, стр. 224].

4. Реализовать цифровую сортировку для типа int (32-разрядных целых чисел). Сортировать по двоичной записи числа [5, стр. 226].

5. Реализовать цифровую сортировку для типа int (32-разрядных целых чисел). Сортировать по десятичной записи числа [5, стр. 226].

6. Реализовать цифровую сортировку для типа int (32-разрядных целых чисел). Сортировать по восьмеричной записи числа [5, стр. 226].

7. Реализовать цифровую сортировку для типа int (32-разрядных целых чисел). Сортировать по шестнадцатеричной записи числа [5, стр. 226].

8. Реализовать пирамидальную сортировку (HeapSort) [5, стр. 178].

9. Реализовать сортировку расческой (CombSort).

10. Реализовать плавную сортировку (Smooth Sort).

11. Реализовать быструю сортировку (QuickSort) [5, стр. 198].

12. Реализовать рандомизированную быструю сортировку (QuickSort) [5, стр. 208].

13. Реализовать блочную (карманную, bucket) сортировку [5, стр. 230].

14. Реализовать метод Patience sorting.

15. Реализовать метод IntroSort.

16. Реализовать бинарный поиск в массиве [1, разд. 2.1].

17. Реализовать поиск i-ой порядковой статистики ([5, стр. 243])

18. Реализовать строгий поиск i-ой порядковой статистики ([5, стр. 247]).

19. Решить методом динамического программирования задачу поиска оптимального пути на конвейере [5, разд. 15.1]

20. Решить методом динамического программирования задачу поиска самой длинной подпоследовательности [5, разд. 15.4]

21. Решить методом динамического программирования задачу поиска лучшего варианта перемножения матриц [5, разд. 15.2]

22. Реализовать гномью сортировку.

23. Реализовать вариант алгоритма Merge Sort без использования дополнительной памяти http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8523

24. Реализовать метод сортировки SpreadSort (http://en.wikipedia.org/wiki/Spreadsort)

25. Реализовать метод сортировки Gapped insertion sort (Library Sort) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.3758

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

Достаточна разработка консольного приложения. Разработка Windows-приложения будет большим преимуществом выполнения работы, если студент достаточно подготовлен для создания Windows-приложений, иллюстрирующих работу системы.

Требования к отчетности по лабораторной работе

В качестве отчета по лабораторной работе студент предоставляет в электронном виде программу на языке C++, реализующую функциональность в соответствии с вариантом задания.

Предлагаемые этапы выполнения работы

1. Изучение теоретического материала.

2. Создание пустого консольного приложения в среде Visual Studio 2005 [3].

3. Разработка функций ввода-вывода данных

4. Отладка функций ввода-вывода данных.

5. Разработка функции сортировки или поиска в соответствии с заданием.

6. Отладка программы.

Теоретический материал, необходимый для выполнения лабораторной работы

Алгоритмы сортировки

В этом разделе описана часть алгоритмов сортировки. Алгоритмы, подробно описанные в [5], не дублируются.

Сортировка вставками

Сортировку вставками необходимо рассмотреть, чтобы перейти затем к сортировке Шелла.

Алгоритм сортировки вставками сводится к следующему. Если первые N элементов (A[0]…A[N-1]) отсортированы, мы можем вставить N-ый элемент в отсортированную последовательность с помощью кода:

t = A[ N ];

for ( i = N - 1; i >= 0 && A[i] > t ; i-- )

A[ i + 1 ] = A[ i ];

A[ i + 1 ] = t;

После этого будут отсортированы уже N+1 элементов.

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

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

Этот алгоритм работает за время O(N²). К его преимуществам относится хорошая работа в случае почти отсортированных массивов (мы мгновенно обнаруживаем, что нам не надо двигать тот или иной элемент) и сохранение порядка элементов при сортировке.

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

Сортировка Шелла [7] – алгоритм, использующий преимущества сортировки вставками и стремящийся избежать его недостатков. На первом этапе выбирается сравнительно большое число K и методом сортировки вставками сортируются массивы

A[0], A[K], A[2K],…

A[0], A[K], A[2K],…

…

A[K-1], A[2K-1], A[3K-1],…

После этого число K уменьшается и выполняется новая сортировка. На последнем этапе (K=1) выполняется обычная сортировка вставками, но, поскольку массив будет почти отсортированным, она будет выполнена очень быстро.

Время работы сортировки Шелла зависит от способа выбора K. Один из наиболее популярных способов выбора значений K это K=2^w-1.

Сортировка шейкером

Сортировка шейкером [8] подобна сортировке пузырьком [1]. Ее отличие заключается в чередовании проходов в одну и другую сторону. На первом шаге мы идем слева направо («тонут» тяжелые элементы), на втором – справа налево («всплывают легкие»), на третьем – снова слева направо и так далее.

На шаге 0 перебираются пары элементов от “0 – 1” до “N-2 – N-1”. На шаге 1 мы знаем, что максимальный элемент уже в позиции N-1 и перебираем пары элементов от «N-3 – N-2» до «0 – 1». На шаге 2 минимальный элемент встал в позицию 0 и нужно перебирать пары элементов от «1 – 2» до «N-3 - N-2».

Сортировка шейкером иллюстрируется на рис. 1.

Рис. 1. Сортировка шейкером.

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