Слободской государственный колледж педагогики и социальных отношений. Специальность: 230115 Программирование в компьютерных системах

Практическая работа №8

Специальность: 230115 Программирование в компьютерных системах.

Дисциплина: Теория алгоритмов.

Тема: Разработка алгоритмов сортировки.

Цель работы:

1. Реализовать изученные алгоритмы сортировки, оценить их эффективность

2. Учиться оформлять алгоритмы решения задач.

Ход работы

Для всех алгоритмов сортировки:

1. составить и записать в отчет блок-схему,

2. программу на языке программирования,

3. произвести оценку эффективности алгоритма

a. Для массива, заполненного случайными элементами

b. Для исходно упорядоченного массива

c. Для массива исходно упорядоченного в обратном порядке.

4. Сделать вывод об эффективности применения каждого алгоритма сортировки в конкретной ситуации.

Список алгоритмов сортировки для исследования

Сортировка выбором (selection sort)

'Очевидный' алгоритм сортировки - перебором находится наименьший элемент, он меняется местами с элементом, стоящим на нулевом месте, затем находится наименьший среди оставшихся и меняется местами с элементом, стоящим на первом месте. Цикл заканчивается, когда будут выбраны все элементы

Пузырьковая сортировка (bubble sort)

Пузырьковая сортировка основана на методе перестановок. В процессе работы очередной элемент сравнивается с соседним и при необходимости выполняется их перестановка.

Сортировка перемешиванием (Cocktail sort)

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

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

Сортировка вставками (insertion sort)

Сортируемый массив просматривается в порядке возрастания номеров и каждый элемент

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

Быстрая сортировка (quick sort)

Алгоритм основан на разделении сортируемого массива на части и перестановке элементов таким образом, чтобы элементы в левой части массива не превосходили элементов в правой. На каждом шаге выбирается 'средний' элемент массива, в результате ряда перестановок он занимает свое законное место, затем каждая из частей упорядочивается.