«Приднестровский государственный университет им. Т.Г. Шевченко»

Рыбницкий филиал

Кафедра физика, математика и информатика

Курсовая работа

по дисциплине: «Структуры и алгоритмы обработки данных»

на тему: « Сортировка выбором связанного списка»

Выполнил:

студент 2 курса

специальности «ПОВТ и АС»

Кравец С.

Проверила:

Старший преподаватель

Глазова Н. С.

г. Рыбница

2012 г.

Содержание

ВВЕДЕНИЕ 3

Глава 1. « сортировка выбором связанного списка» 4

Глава 2. Реализация приложения «сортировка выбором связанного списка» 7

2.1. Постановка задачи 7

2.2. Описание технологии разработки 7

2.2.Экспериментальный раздел 8

ЗАКЛЮЧЕНИЕ 11

СПИСОК ЛИТЕРАТУРЫ 12

Введение

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

Один из них «Сортировка выбором связанного списка». Цель курсовой работы является изучение сортировки выбора на примере связанного списка.

Задачи:

• Изучить теоретические аспекты для реализации приложения « Сортировка выбором связанного списка».

• Реализовать алгоритм «Сортировка выбором связанного списка».

• Провести анализ работоспособности программного продукта реализующего «  Сортировка выбором связанного списка».

Глава 1. « сортировка выбором связанного списка»

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

Основным критерием для классификации алгоритмов сортировки является их быстродействие. При сортировке выполняются два типа операций - сравнение ключей и перестановка элементов (в случае со связными списками - переназначение указателей). Если в массиве n элементов, то алгоритм считается хорошим, если число перестановок равно произведению числа элементов массива n на логарифм этого числа log(n). Например, стандартная пузырьковая сортировка требует числа перестановок, равного квадрату от n.

Методы сортировки можно разбить на три основных класса:

• сортировка включениями;

• сортировка выбором;

• сортировка обменом.

Принцип, лежащий в основе первого класса, заключается в том, что массив разбивается на две половины - итоговую и входную. Берется элемент из входной половины и вставляется в итоговую в порядке сортировки. Число перестановок элементов в общем случае равно квадрату от n.

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

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

Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.

На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на Рис.1

Рис.1. Последовательность шагов.

Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

Для нахождения наименьшего элемента из n+1 рассматриваемый алгоритм совершает n сравнений. С учетом того, что количество рассматриваемых на очередном шаге элементов уменьшается на единицу, общее количество операций:

n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = Theta(n2).

Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки растет квадратично относительно количества элементов.

Алгоритм не использует дополнительной памяти: все операции происходят "на месте".

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

Рис.2. Сортировка последовательности по первому полю.

Результат ее сортировки можно увидеть уже после шага 0, так как больше обменов не будет. Порядок ключей 2a, 2b был изменен на 2b, 2a, так что метод неустойчив.

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