Методы сортировки. Их сравнительный анализ (стр. 1 из 4)
Министерство Науки и Образования УкраиныХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ
Кафедра Информатики
Пояснительная записка
КУРСОВАЯ РАБОТА
ПО КУРСУ
“Объектно-ориентированное программирование на VisualC ++”
на тему: "Методы сортировки. Их сравнительный анализ"
Выполнил: Проверил:
Ст. гр. СУА-03-1 старший преподаватель
Котляров М.Н. Бритик В.И.
Харьков 2004
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 Решение интеллектуальной задачи на компьютере
2 ПОСТРОЕНИЕ АЛГОРИТМА КОДИРОВАНИЯ НА VISUALC++
2.1 Алгоритм решения задачи
2.2 Описание программы “Sort”
3 Инструкции пользователя
ЗАКЛЮЧЕНИЕ
Приложение
ЛИТЕРАТУРА И ИСТОЧНИКИ
РЕФЕРАТ
Записка пояснительная к курсовой работе содержит: 24 стр.
Предмет исследования - современные методы разработки программ таких, как объектно-ориентированное программирование и визуальное проектирование, а также структурное и модульное программирование.
Цель курсовой работы - систематизация, углубление и активное применение знаний по системному программированию, закрепление знаний, полученных в лекционном курсе, а также на практических и лабораторных занятиях.
Метод исследования - изучение литературы, составление и отладка программ на компьютере.
Программа типа “Sort” может использоваться, как программа, предназначенная для сортировки элементов массива.
Разработан проект “Sort” полностью соответствующий условию задания и имеющий довольно удобный интерфейс.
КЛЮЧЕВЫЕ СЛОВА: SORT, VisualC++, функция, проект, сообщение, программа.
ВВЕДЕНИЕ
В настоящее время вычислительная техника проникла практически во все сферы человеческой деятельности. С помощью ЭВМ можно решать самые разные задачи. Но для того, чтобы решить поставленную задачу, необходимо указать последовательность действий, выполнение которых приведёт к требуемому результату, – составить программу. Для удобства работы с ЭВМ эта операция производится с помощью языков программирования (высокого или низкого уровня).
Один из широко используемых языков программирования - это Visual C++, который можно использовать для написания программ, работающих в операционной среде Windows. На данное время одной из самых распространенных его версий является Microsoft Visual C++, и среда программирования Microsoft Developer Studio 6.0.
Среда программирования Microsoft Developer Studio 6.0 позволяет создавать тексты программ, компилировать их, находить ошибки и оперативно их исправлять; компоновать программы из отдельных частей, включая стандартные модули, отлаживать и выполнять отлаженную программу.
Используя перечисленные возможности, можно создавать различные прикладные программы, например, такие, как программа, написанная при выполнении данной курсовой работы.
1Решение интеллектуальной задачи на компьютере
В данном курсовом проекте необходимо разработать программу типа "Sort", с помощью которой можно производить сортировку массива различными методами. В частности в данном курсовом проекте используются следующие методы: “Обменная сортировка с разделением (quicksort)”, “Метод Шелла” и “Метод прямого обмена (Пузырька)”. Программа должна иметь удобный интерфейс.
2 ПОСТРОЕНИЕ АЛГОРИТМА КОДИРОВАНИЯ НА VISUALC++
Среда VisualC++ - это сложный механизм, обеспечивающий высокоэффективную работу программиста. Создание прикладных программ, или приложений выполняется в интегрированной среде разработки IDE (IntegratedDevelopmentEnvironment). IDE служит для организации взаимодействия с программистом и включает ряд окон, содержащих различные управляющие элементы. С помощью средств интегрированной среды разработчик может проектировать интерфейсную часть приложения, а также писать программный код и связывать его с управляющими элементами. При этом вся работа по созданию приложения, включая отладку, происходит в IDE.
Интегрированная среда разработки VisualC++ представляет собой многооконную систему. Вид интегрированной среды разработки (интерфейс) может различаться в зависимости от настроек. Кроме стандартных окон, на экране могут присутствовать и другие окна, отображаемые при вызове соответствующих средств, например, ImageEditor (Редактор изображений). Окна VisualC++ (но не главное) можно перемещать, убирать с экрана, а также изменять их размеры.
Несмотря на наличие многих окон, VisualC++ является одно-документной средой, т.е. позволяет одновременно работать только с одним приложением (проектом приложения). Название проекта приложения выводится в строке заголовка главного окна в верхней части экрана.
Если свернуть главное окно, то происходит минимизация всего интерфейса VisualC++ и, соответственно, всех открытых окон. При закрытии главного окна работа с VisualC++ прекращается.
Самой последней и наиболее усовершенствованной версией стал MicrosoftVisualC++ 6.0. VisualC++ 6.0, вобрав в себя всё самое лучшее от предыдущих версий, предоставляет ряд новых возможностей. Так, например, стал более удобным и современным интерфейс среды программирования, создаваемые VisualC++программы учитывают архитектуру современных процессоров, существенно расширены возможности отладчика.
VisualC++ 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"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.