Реферат: Иследование методов сортировки Метод пузырька и Метод простых вставок

К первой группе относятся такие методы, как метод выборки, "пузырька", вставки, Шелла. Ко второй группе относятся метод квадратичной выборки, метод слияния и другие. Простые методы сортировки (выбором, обменом, вставкой) требуют приблизительно n**2 сравнений.

Более сложные алгоритмы обычно обеспечивают получение результата за n*log2(n) сравнений в среднем: сортировка методом Шелла, слиянием, "быстрая сортировка". Однако оптимальной в любом случае сортировки не существует, так как их эффективность существенно зависит от типа ключей в массиве и их предварительной упорядоченности.
Рассмотрим алгоритмы наиболее распространенных методов внутренней сортировки ( упорядочение выполняется по возрастанию значений ключа ).

5.2.Метод "Пузырька".

При использовании этого способа требуется самое большее (n-1) проходов. В течение первого прохода массива сравниваются ключи К1 и К2 первой и второй записей, и, если порядок между ними нарушен, то записи R1 и R2 меняются местами. Затем этот процесс повторяется для записей R2 и R3, R3 и R4 и т.д. Данный метод заставляет двигаться, или "всплывать", записи с малыми ключами. После первого прохода запись с наибольшим ключом будет находиться на n - й позиции массива. При каждом последующем проходе записи со следующем наибольшим ключом будут располагаться в позициях n-1, n-2, ... , 2 соответственно, в результате чего будет сформирована отсортированная таблица. После каждого прохода через массив может быть сделана проверка, были ли совершены перестановки в течение данного прохода. Если перестановок не было, то это означает, что массив уже отсортирован и дальнейших проходов не требуется. Кроме того, можно запоминать индекс последней перестановки. Это позволит уменьшить на следующем шаге просматриваемый массив.
Характеристики сортировки методом "пузырька" в худшем случае составляют n(n-1)/2 сравнений и n(n-1)/2 перестановок (худшим считается случай,когда элементы наиболее удалены от своих конечных позиций). Среднее число сравнений и перестановок имеет порядок n**2 . Сортировка пузырьковым методом использует метод обменной сортировки.

Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой когда каждый пузырек находит свой собственный уровень.

Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.

5.3 Метод простых вставок

Сортировка вставками - простой алгоритм сортировки. Этот метод сортировки менее эффективен чем более сложные алгоритмы ( такие как быстрая сортировка), но у него есть ряд преймушеств:

· Прост в реализации

· Эффективен на небольших наборах данных

· Эффективен на наборе данных которые уже частично отсортированы

· Это устойчивый алгоритм (не меняет порядок элеменов которые уже осотрированны)

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

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

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

4 ВЫВОДЫ

В ходе выполнения данного курсового проекта были разработана программа на языке высокого уровня Delphi 7. А также изучены возможности данного языка.

Систематизированы и закреплены практические навыки использования ЭВМ, программного обеспечения, существующих средств обслуживания системных программистов, а также теоретические знания по основным разделам курса "Объектно-ориентированного программирования". Основное внимание уделено изучению современных методов защиты информации, способов проектирования приложений, объектно-ориентированному и системному программированию.

При выполнении курсового проекта произведено знакомство с реферативными журналами и другими информационными источниками по объектно-ориентированному и системному программированию с целью анализа состояния решаемой задачи.

Получены практические навыки работы в средеDelphi 7.

ПРИЛОЖЕНИЕ А

Формы программы

На рисунке 1.1 изображено главное меню программы:

Рис 1.1

На рисунке 1.2 показано окно сравнения методов сортировки:

Рис. 1.2

На рис. 1.3 показано окно “О программе”

ПРИЛОЖЕНИЕ Б

Программа имеет возможность сохранять обрабатываемые данные в файл * txt.Сохранение производится в текстовый файл, который можно открыть с помощью любого текстового редактора.

Также программа вводит исходный массив из файла * txt который создается пользователем самостоятельно в любом текстовом редакторе. При создании исходного массива нужно придерживаться следующих правил:

· Файл должен содержать только числовую информацию.

· Первая цифра должна соответствовать количеству элементов массива, и после этой цифры пользователь должен перейти на новую строку (Enter).

· После перехода на новую строку, пользователь вводит нужный ему одномерный массив и сохраняет его под любым именем в формате *txt.