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

Посмотреть архив целиком

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

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

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





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



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

ПО КУРСУ

Объектно-ориентированное программирование на Visual C ++”

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









Выполнил: Проверил:

Ст. гр. СУА-03-1 старший преподаватель

Котляров М.Н. Бритик В.И.









Харьков 2004





СОДЕРЖАНИЕ



ВВЕДЕНИЕ

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

Приложение

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







РЕФЕРАТ



Записка пояснительная к курсовой работе содержит: 24 стр.

Предмет исследования - современные методы разработки программ таких, как объектно-ориентированное программирование и визуальное проектирование, а также структурное и модульное программирование.

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

Метод исследования - изучение литературы, составление и отладка программ на компьютере.

Программа типа “Sort” может использоваться, как программа, предназначенная для сортировки элементов массива.

Разработан проект “Sort” полностью соответствующий условию задания и имеющий довольно удобный интерфейс.

КЛЮЧЕВЫЕ СЛОВА: SORT, Visual C++, функция, проект, сообщение, программа.





ВВЕДЕНИЕ


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

Один из широко используемых языков программирования - это 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 . Сортировка пузырьковым методом использует метод обменной  сортировки. Она основана на выполнении в цикле операций сравнения   и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с  водой когда каждый пузырек находит свой собственный уровень.


Случайные файлы

Файл
14049.rtf
79360.rtf
LEKS_17.DOC
28268.rtf
90247.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.