Методы внутренней сортировки Обменная сортировка Сравнение с другими методами сортировки

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУРСОВАЯ РАБОТА

по дисциплине «Алгоритмическое обеспечение ЭВС»

на тему «Методы внутренней сортировки. Обменная сортировка.

Сравнение с другими методами сортировки»

2010 г.

Содержание

Введение

1. Сортировка включением

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

3. Обменная сортировка

4. Сортировка выбором

5. Сортировка разделением

6. Сравнение методов

Заключение

Приложение

Литература

Введение

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

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

1. Сортировка включением

Одним из наиболее простых и естественных методов внутренней сортировки является сортировка с простыми включениями. Идея алгоритма очень проста. Пусть имеется массив ключей a[1], a[2], ..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2] ...) и до тех пор, пока для очередного элемента a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такой элемент a[j], что a[j] <= a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).

Легко видеть, что в лучшем случае (когда массив уже упорядочен) для выполнения алгоритма с массивом из n элементов потребуется n-1 сравнение и 0 пересылок. В худшем случае (когда массив упорядочен в обратном порядке) потребуется n?(n-1)/2 сравнений и столько же пересылок. Таким образом, можно оценивать сложность метода простых включений как O(n2).

Можно сократить число сравнений, применяемых в методе простых включений, если воспользоваться тем фактом, что при обработке элемента a[i] массива элементы a[1], a[2], ..., a[i-1] уже упорядочены, и воспользоваться для поиска элемента, с которым должна быть произведена перестановка, методом двоичного деления. В этом случае оценка числа требуемых сравнений становится O(n?log n). Заметим, что поскольку при выполнении перестановки требуется сдвижка на один элемент нескольких элементов, то оценка числа пересылок остается O(n2).

Таблица 1.1 Пример сортировки методом простого включения

Начальное состояние массива	8 23 5 65 44 33 1 6
Шаг 1	8 23 5 65 44 33 1 6
Шаг 2	8 5 23 65 44 33 1 6 5 8 23 65 44 33 1 6
Шаг 3	5 8 23 65 44 33 1 6
Шаг 4	5 8 23 44 65 33 1 6
Шаг 5	5 8 23 44 33 65 1 6 5 8 23 33 44 65 1 6
Шаг 6	5 8 23 33 44 1 65 6 5 8 23 33 1 44 65 6 5 8 23 1 33 44 65 6 5 8 1 23 33 44 65 6 5 1 8 23 33 44 65 6 1 5 8 23 33 44 65 6
Шаг 7	1 5 8 23 33 44 6 65 1 5 8 23 33 6 44 65 1 5 8 23 6 33 44 65 1 5 8 6 23 33 44 65 1 5 6 8 23 33 44 65

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

Дальнейшим развитием метода сортировки с включениями является сортировка методом Шелла, называемая по-другому сортировкой включениями с уменьшающимся расстоянием. Мы не будем описывать алгоритм в общем виде, а ограничимся случаем, когда число элементов в сортируемом массиве является степенью числа 2. Для массива с 2n элементами алгоритм работает следующим образом. На первой фазе производится сортировка включением всех пар элементов массива, расстояние между которыми есть 2(n-1). На второй фазе производится сортировка включением элементов полученного массива, расстояние между которыми есть 2(n-2). И так далее, пока мы не дойдем до фазы с расстоянием между элементами, равным единице, и не выполним завершающую сортировку с включениями. Применение метода Шелла к массиву, используемому в наших примерах, показано в таблице 2.2.

Таблица1.2. Пример сортировки методом Шелл

Начальное состояние массива

8 23 5 65 44 33 1 6

Фаза 1 (сортируются элементы, расстояние между которыми четыре)

8 23 5 65 44 33 1 6

8 23 1 65 44 33 5 6

8 23 1 6 44 33 5 65

Фаза 2 (сортируются элементы, расстояние между которыми два)

1 23 8 6 44 33 5 65

1 23 8 6 5 33 44 65

1 23 5 6 8 33 44 65

1 6 5 23 8 33 44 65

1 6

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать Курсовые работы по информатике и программированию МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КУРСОВАЯ РАБОТА по дисциплине «Алгоритмическое обеспечение ЭВС» на тему «Методы внутренней

Оценок: 1000 (Средняя 5 из 5)

Наверняка у вас есть товары или услуги, продажа которых приносит вам максимальную прибыль. Для быстрого старта в сети вам необходимо создание посадочной страницы (одностраничного сайта), на которой будет размещена информация о маржинальных товарах/услугах интернет магазина. За 8 лет опыта разработки конверсионных страниц мы выработали оптимальную структуру, которая позволит привлекать через landing page больше продаж. На такую структуру «одевается» ваш контент — фирменный стиль, тексты, фотографии, уникальные торговые предложения, после чего страница выходит в свет. Разработка лендинга и запуск в сети — до 7 рабочих дней. Стоит отметить, что в разработку самой посадочной страницы входит и написание копирайтером продающих текстов для вашего бизнеса, чтобы каждый посетитель страницы захотел совершить покупку именно у вас. Результат: качественно разработаная продающая посадочная страница, которая готова приносить вам новых клиентов.