Методы сортировки. Их сравнительный анализ

2

Министерство Науки и Образования Украины

ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ

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

Пояснительная записка

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

2 ПОСТРОЕНИЕ АЛГОРИТМА КОДИРОВАНИЯ НА VISUALC++

2.1 Алгоритм решения задачи

2.2 Описание программы “Sort”

3 Инструкции пользователя

ЗАКЛЮЧЕНИЕ

Приложение

ЛИТЕРАТУРА И ИСТОЧНИКИ

РЕФЕРАТ

ВВЕДЕНИЕ

В настоящее время вычислительная техника проникла практически во все сферы человеческой деятельности. С помощью ЭВМ можно решать самые разные задачи. Но для того, чтобы решить поставленную задачу, необходимо указать последовательность действий, выполнение которых приведёт к требуемому результату, - составить программу. Для удобства работы с ЭВМ эта операция производится с помощью языков программирования (высокого или низкого уровня).

Один из широко используемых языков программирования - это Visual C++, который можно использовать для написания программ, работающих в операционной среде Windows. На данное время одной из самых распространенных его версий является Microsoft Visual C++, и среда программирования Microsoft Developer Studio 6.0.

Среда программирования Microsoft Developer Studio 6.0 позволяет создавать тексты программ, компилировать их, находить ошибки и оперативно их исправлять; компоновать программы из отдельных частей, включая стандартные модули, отлаживать и выполнять отлаженную программу.

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

1 Решение интеллектуальной задачи на компьютере

В данном курсовом проекте необходимо разработать программу типа "Sort", с помощью которой можно производить сортировку массива различными методами. В частности в данном курсовом проекте используются следующие методы: “Обменная сортировка с разделением (quicksort)”, “Метод Шелла” и “Метод прямого обмена (Пузырька)”. Программа должна иметь удобный интерфейс.

2 ПОСТРОЕНИЕ АЛГОРИТМА КОДИРОВАНИЯ НА VISUAL C++

Среда Visual C++ - это сложный механизм, обеспечивающий высокоэффективную работу программиста. Создание прикладных программ, или приложений выполняется в интегрированной среде разработки IDE (Integrated Development Environment). IDE служит для организации взаимодействия с программистом и включает ряд окон, содержащих различные управляющие элементы. С помощью средств интегрированной среды разработчик может проектировать интерфейсную часть приложения, а также писать программный код и связывать его с управляющими элементами. При этом вся работа по созданию приложения, включая отладку, происходит в IDE.

Интегрированная среда разработки Visual C++ представляет собой многооконную систему. Вид интегрированной среды разработки (интерфейс) может различаться в зависимости от настроек. Кроме стандартных окон, на экране могут присутствовать и другие окна, отображаемые при вызове соответствующих средств, например, Image Editor (Редактор изображений). Окна Visual C++ (но не главное) можно перемещать, убирать с экрана, а также изменять их размеры.

Несмотря на наличие многих окон, Visual C++ является одно-документной средой, т.е. позволяет одновременно работать только с одним приложением (проектом приложения). Название проекта приложения выводится в строке заголовка главного окна в верхней части экрана.

Если свернуть главное окно, то происходит минимизация всего интерфейса Visual C++ и, соответственно, всех открытых окон. При закрытии главного окна работа с Visual C++ прекращается.

Самой последней и наиболее усовершенствованной версией стал Microsoft Visual C++ 6.0. Visual C++ 6.0, вобрав в себя всё самое лучшее от предыдущих версий, предоставляет ряд новых возможностей. Так, например, стал более удобным и современным интерфейс среды программирования, создаваемые Visual C++ программы учитывают архитектуру современных процессоров, существенно расширены возможности отладчика.

Visual C++ 6.0 может работать в среде операционных систем от Windows 95 до Windows 2000. Особенных требований к компьютеру система не предъявляет, за исключением того, что процессор должен быть типа Pentium, оперативной памяти - не менее 32 Мбайт и достаточное количество свободной дисковой памяти (порядка 200 Мбайт).

2.1 Алгоритм решения задачи

Основными операциями, выполняемыми над массивами, являются упорядочение (сортировка) записей и поиск в массиве  записи по заданному условию( по ключу ). Сортировка является операцией расстановки записей массива в определенном порядке в соответствии с некоторым критерием упорядочения. Сортировка осуществляется в соответствии со значением ключей всех записей (напр., упорядочение фамилий по алфавиту или чисел по возрастанию ). Существует достаточно много методов     сортировки, принципиально отличающихся друг от друга. Если массив целиком помещается в оперативной памяти ЭВМ, то его упорядочение называют внутренним. Если для хранения упорядочиваемых данных используются внешнее запоминающее устройство, то такое упорядочение называют внешним. Критериями оценки методов сортировки являются:

С -    количество операций сравнения пар ключей,

   Р -    число перестановок элементов ,

   S -    резерв памяти.

Среднее количество операций    сравнения зависит от    метода сортировки и при рациональном выборе метода достигает некоторого минимума, зависящего от n - размера массива (размер массива - количество содержащихся в нём записей). Методы внутренней сортировки можно разделить на две группы:

- методы, не требующие резерва памяти;

- методы, требующие резерва памяти.

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

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

При использовании этого способа требуется самое большее (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"), очень медленно достигает своего места.     Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении.    В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Хотя эта сортировка является улучшением пузырьковым методом,  ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.

· Метод Шелла.

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

При поверхностном взгляде на алгоритм нельзя сказать, что он  дает хороший результат и даже то, что в результате получится отсортированный массив.    Однако, он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы  массива уже находятся в относительном порядке, а упорядоченность   увеличивается при каждом новом просмотре данных.

Расстояния между сравниваемыми элементами могут изменяться  по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3, 2, 1, которая использована в данной курсовой работе. Следует избегать последовательностей степени  двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки. /Однако, при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно. Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая  должна сортироваться. Управляющие элементы имеют граничные для   массива данных значения, т.е. наименьшее и наибольшее значения. В  этом случае не обязательно выполнять проверку на граничные значения. Однако, применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки. Анализ сортировки Шелл требует решения некоторых сложных   математических задач. Время  выполнения сортировки    Шелла пропорционально n**1.2. Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки. Однако, прежде   чем вы решите использовать сортировку Шелла, следует иметь в виду, что быстрая сортировка дает даже еще лучшие результаты.

Страницы: 1, 2