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

Введение

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 Пример сортировки методом простого включения