/> Министерство Науки и ОбразованияУкраины
ХАРЬКОВСКИЙ НАЦИОНАЛЬНЫЙУНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ
Кафедра Информатики
Пояснительная записка
КУРСОВАЯ РАБОТАПО КУРСУ
“Объектно-ориентированноепрограммирование на VisualC++”
на тему: «Методы сортировки. Ихсравнительный анализ»Выполнил: Проверил:Ст. гр. СУА-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 ПОСТРОЕНИЕАЛГОРИТМА КОДИРОВАНИЯ НА VISUALC++
Среда 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 до Windows2000. Особенных требований к компьютеру система не предъявляет, за исключениемтого, что процессор должен быть типа 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. Эта зависимостьзначительно лучше квадратичной зависимости, которой подчиняются рассмотренныеранее алгоритмы сортировки. Однако, прежде чем вы решитеиспользовать сортировку Шелла, следует иметь в виду, что быстрая сортировкадает даже еще лучшие результаты.
В рассмотренных алгоритмах сортировки запись перемещается каждый разтолько на одну позицию. При этом среднее время работы будет в лучшем случаепропорционально n. Методом, существенно превосходящим простые вставки, прикотором записи перемещаются большими скачками, является метод Шелла (сортировкас убывающим шагом). Метод состоит в том, что упорядоченный массив разделяетсяна группы элементов, каждая из которых упорядочивается методом вставки. В процессеупорядочения размеры таких групп увеличиваются до тех пор, пока все элементымассива не войдут в упорядоченную группу. Выбор очередной упорядочиваемойгруппы и ее расположение внутри массива производятся так, чтобы можно былоиспользовать предшествующую упорядоченность. Группой массива называют последовательностьэлементов, номера которых образуют арифметическую прогрессию с разностью h (hназывают шагом группы). В начале процесса упорядочения выбирается первый шаггруппы h1, который зависит от размера таблицы. Шелл предложил брать
h1=[n/2], а hi=h((i-1)/2).
В более поздних работах Хиббард показал, что для ускорения процессацелесообразно определить шаг h1 по формуле:
h1=2**k+1, где 2**k
После выбора h1 методом вставки упорядочиваются группы, содержащиеэлементы с номерами позиций
i, i+h1, i+2*h1, ..., i+mi*h1.
При этом i=1,2,...,h1; m[i] — наибольшее целое,удовлетворяющее неравенству i+m[i]*hi
Затем выбирается шаг h2h2>...>hl). Этот последний этап представляет собойупорядочение всего массива методом вставки. Но так как исходный массивупорядочивался отдельными группами с последовательным объединением этих групп,то общее количество сравнений значительно меньше, чем n/4, требуемое при методе вставки. Число операций сравнения пропорциональноn*(log2(n))**2 .
· Обменнаясортировка с разделением (Quicksort).
Данный метод является одним из лучших методов внутренней сортировки ивесьма эффективен для больших массивов. Целью каждого шага в данном методеявляется помещение очередной рассматриваемой записи на конечную позицию внутримассива. Если поступать таким способом, то все записи, предшествующие данной,будут иметь меньший ключ, в то время как все последующие — больший. Прииспользовании такого метода массив всегда делится на два подмассива.Анологичный процесс может быть применен к каждому из этих подмассивов и повторятьсядо тех пор, пока все записи не будут установлены на их конечные позиции. Используютсядва индекса i и j с начальными значениями границ массива. Сравниваются ключиK[i] и K[j], и если перестановка не требуется, то j уменьшается на 1, и процессповторяется. В том случае, когдаK[i]>=K[j], записи R[i] и R[j] меняются местами. Затем этот процессповторяется с i, увеличенным на 1, и фиксированным j до тех пор, пока невозникает другая перестановка. В этот момент j снова будет уменьшено на 1, а iостанется фиксированным, и т.д. Процесс выполняется до тех пор, пока i
Каждый раз массив разбивается на два подмассива, один из которыхобрабатывается, в то время как границы второго запоминаются стем, чтобы он был обработан позже. В этих целях можетбыть использован стек, представляющий собой матрицу из двух столбцов. В первомстолбце хранятся нижние границы разделяемых подмассивов, во втором — верхниеграницы. Всякий раз один из полученных в результате разделения подмассивовподвергается дальнейшему разделению, а границы другого помещаются в свободнуюстроку стека (обычно в стек помещаются границы большего по длине массива,поскольку это уменьшает требуемый размер стека). Как только завершается процессразделения текущего подмассива, т.е. ее длина станет меньше трех, дляразделения берется подмассив, границы которого были занесены в стек последними.Строка стека, в которой хранились эти границы, освобождается. Процессупорядочения завершается, когда стек полностью освобождается.
Разделение следует применять для подмассивов, длина которых больше 9, а короткие подмассивы упорядочивать методом вставки.
Стек занимает мало места. Например, стек из 20 строк позволяетупорядочить массив, содержащую до 10**7 записей. Кроме того, в современныхязыках программирования при работе рекурсивных программзанесение и извлечение из стека выполняется автоматически, поэтомурекомендуется использовать именно этот механизм. Среднее число сравнений дляданного алгоритма составляет n*log(n) где n — число записей в сортируемоммассиве, m — размер подмассива, сортируемой методом вставки.
Наихудшей ситуацией при использовании рассмотренного алгоритма являетсяслучай, когда массив уже отсортирован. При этом число сравнений порядка n, т.е.алгоритм не лучше сортировки выборкой.
2.2Описание программы “Sort”
Данный проект создавался с помощью AppWizard – генератором кода, создающимрабочую заготовку Windows-приложенияс теми компонентами, именами классов и исходными файлами, что были указанычерез диалоговые окна. В частности: в закладке Project выбираем — MFC AppWizard (exe). Затем нужно пройти серию экранов AppWizard:
Step 1: выбираем“Single document”
Step2: оставляем без изменения
Step 3: без изменения
Step 4: оставляем только флажки“3D controls”, “Docking ToolBar”
Step 5: устанавливаем “As a statically linked library”
Step6: отображает информацию о созданных классах
После этого AppWizardсгенерирует код для поддержки функциональных возможностей программы на базебиблиотеки MFC, т.е. создаст каркас приложения.Рассмотрим некоторые элементы программы, созданные на данном этапе:
Класс CSortApp. Объект класса CSortApp представляет программу. В программеопределяется единственный глобальный объект класса CSortApp – theApp. Базовый класс CWinApp определяет основные характеристики объекта theApp.
Класс CSortView. Объект класса CSortView представляет основное окнопрограммы. Когда конструктор вызывает функцию-член Create базового класса CFrameWnd, Windows создаёт действительнуюоконную структуру, а каркас приложения связывает её с C++-объектом. Функции ShowWindow и UpdateWindow, являющиеся также функциями-членамибазового класса, вызываются для вывода окна на экран.
При запуске проекта операционнаясистема вызывает в программе функцию WinMain, а та ищет глобально сконструированный объект класса,производного от CWinApp. В любомприложении, в том числе и в “Sort”,обязательно должна присутствовать эта функция, на которую возлагается рядспецифических задач. И самая важная – создание основного окна программы, скоторым должен быть связан код, способный обрабатывать сообщения, передаваемыеоперационной системой этому окну. В нашем случае при программировании на Microsoft Visual C++ 6.0, с библиотекой классов Microsoft Foundation Class (MFC) Library 6.0, эта функция скрыта внутрикаркаса приложения и нет необходимости в её написании, но необходимо понимать,что именно с помощью неё осуществляется связь между операционной системой ипрограммой.
Библиотека MFC прямоподдерживает около 140 функций, обрабатывающих Windows-сообщения. Кроме того, можно определять своисобственные сообщения, связанные с обработчиками команд меню, элементовуправления и т.д. В программе “Sort” используется более 40 функций, методов и сообщений Windows. Ниже они перечислены в порядке ихпоявления в программе с кратким описанием:
Format– преобразует типы переменных;
InvalidateRect и Invalidate – обновляют рабочую область и генерируют сообщение WM_PAINT;
DestroyWindow – разрушает окно;
PostQuitMessage – посылает окну сообщение WM_DESTROY;
ShowWindow –отображает или скрывает окно;
UpdateWindow – заставляет окно перерисовать своё содержимое;
TextOut –вывод текста на экран;
После вызова функции UpdateWindow, окно окончательно выведено на экран. Теперь программа должнаподготовить себя для получения информации от пользователя через клавиатуру имышь. Windows поддерживает “очередь сообщений” (message queue) для каждой программы, работающей в данный момент всистеме Windows. Когда происходит ввод информации, Windows преобразует её в “сообщение”,которое помещается в очередь сообщений программы. Каждое получаемое окномсообщение идентифицируется номером, который содержится в параметре message оконной процедуры. В заголовочныхфайлах Windows определены идентификаторы,начинающиеся с префикса WM (“window message”) для каждого типа сообщений. Ниже приведены всесообщения используемые в курсовом проекте:
Сообщение WM_CREATE – это первое сообщение, которое Windows посылает объекту View. Оно передаётся, когда каркасприложения вызывает оконную функцию Create, т.е. в тот момент, когда создание окна ещё не закончено и его не виднона экране. Следовательно, обработчик OnCreate пока не может обращаться к Windows-функциям, доступным только после отображения окна.Такие функции можно вызвать из замещённой функции OnInitialUpdate.
Функция-членOnDraw().Это виртуальная функция-член класса CView; каркас приложений вызывает её всякий раз, когдаприходит сообщение о том, что нужно перерисовать окно отображения. А такаянеобходимость возникает при масштабировании окна или при появлении ранеескрытой его части, или при изменении программой данных, связанных с этим окном.В первых двух случаях каркас приложения вызывает OnDraw, но если какая-то функция в программе изменяетданные, она должна уведомить об этом Windows, вызвав наследуемую функцию-член Invalidate (или InvalidateRect) для данной области отображения.Вызов Invalidate приводит впоследствии кавтоматическому вызову OnDraw.
Windowsне разрешает прямой доступ к видеооборудованию, обращение к нему проходит черезтак называемый контекст устройства (device context),сопоставленный с конкретным окном. В библиотеке MFC контекст устройства – это С++-объект класса CDC, передаваемый функции OnDraw (по указателю) как параметр. Получивуказатель на контекст устройства, можно вызывать множество функций-членов CDC, которые и выполняют всю работу порисованию.
В данном курсовом проекте при вызове функции OnDraw происходит вывод исходного и отсортированного массивана экран, а также информации о количестве перестановок произведённых во времясортировки.
Когда пользователь выбирает пункт меню, Windows посылает программе сообщение WM_COMMAND,содержащее идентификатор этого пункта меню в младшем слове параметра сообщения.Ниже рассмотрены идентификаторы, соответствующее пунктам меню программы:
ID_QUIK – это идентификатор пункта “Обменная сортировка с разделением (quicksort)” в меню. Выбор этого пунктаприводит к сортировке массива данным методом.
ID_SHELL – это идентификатор пункта “МетодШелла” в меню. Выбор этого пункта приводит к сортировке массива методом Шелла.
ID_PUZIROK – этому идентификатору в менюсоответствует пункт “Метод прямого обмена (Пузырька)”. Выбор этого пунктаприводит к сортировке массива методом “Пузырька”.
Выбор пункта меню “О программе…”, которому соответствует идентификатор ID_APP_ABOUT,выведет модальное окно диалога, в котором содержится краткая информация оразработчике и программе.
ID_APP_EXIT – этому идентификатору в меню соответствует пункт“Выход”. При выборе этого пункта происходит вызов функции OnDestroy, что приводит к разрушению окна изавершению работы с программой.
3ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ
Запуск программы осуществляется при открытии файла Sort.exe, который находится на дискете. При этом на экранепоявиться окно, в левой верхней части которого будет видна надпись “Методысортировки” – это имя программы. Ниже располагается меню, с помощью которогоможно выполнить различные действия с данным приложением. При нажатии на пунктеменю “Файл”, выпадет, так называемое, всплывающее меню, в котором находитсяпункт “Выход”. При выборе этого пункта программа закрывается.
Следующий пункт главного меню – это “Сортировка”, подменю которогосодержит пункты “Обменная сортировка с разделением (quicksort)”, “Метод Шелла”и “Метод прямого обмена (Пузырька)”. Выбор первого пункта позволяет произвестисортировку массива методом “Обменной сортировки с разделением”. Нажатие напункте меню “Метод Шелла” приводит к сортировке массива методом Шелла. И выборпоследнего подпункта меню сортирует массив методом “Пузырька”.
Последним пунктом меню является “Помощь”. Если выбрать этот пункт, то вподменю можно увидеть пункт: “О программе”, который содержит информацию оразработчике и о самой программе.
Под меню располагается панель инструментов, которая дублирует все пунктыосновного меню. Ещё ниже расположена клиентская область, в которой происходитвесь вывод информации.
Системные требования: Pentium 133, 16 MB RAM, Windows 95/98/2000 NT/XP.
ЗАКЛЮЧЕНИЕ
В ходе выполнения данного курсового проекта были разработана программа наязыке высокого уровня Visual C++. А такжеизучены возможности данного языка.
Систематизированы и закреплены практические навыки использования ЭВМ,программного обеспечения, существующих средств обслуживания системныхпрограммистов, а также теоретические знания по основным разделам курса«Объектно-ориентированного программирования». Основное вниманиеуделено изучению современных методов защиты информации, способов проектированияприложений, объектно-ориентированному и системному программированию.
При выполнении курсового проекта произведено знакомство с реферативнымижурналами и другими информационными источниками по объектно-ориентированному исистемному программированию с целью анализа состояния решаемой задачи.
Получены практические навыки работы в средеVisual C++.
ПРИЛОЖЕНИЕ
#include «stdafx.h»
#include «Sort.h»
#include «SortDoc.h»
#include «SortView.h»
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
//объявление глобальных переменных
int mas[20]={30,5,17,8,1,14,12,3,77,2,45,89,33,21,6},mas2[20], kol=15, count=0;
CString str;
bool sort=false;
int metod=0;
//1- quicksort
//2- shell
//3- пузырька
/////////////////////////////////////////////////////////////////////////////
// CSortView
IMPLEMENT_DYNCREATE(CSortView, CView)
BEGIN_MESSAGE_MAP(CSortView, CView)
//{{AFX_MSG_MAP(CSortView)
ON_COMMAND(ID_QUICK, OnQuick)
ON_COMMAND(ID_PUZIROK, OnPuzirok)
ON_COMMAND(ID_SHELL, OnShell)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()
/////////////////////////////////////////////////////////////////////////////
// CSortView construction/destruction
CSortView::CSortView()
{
// TODO: add construction code here
}
CSortView::~CSortView()
{
}
BOOL CSortView::PreCreateWindow(CREATESTRUCT& cs)
{
// TODO: Modify the Window class or styles here bymodifying
// the CREATESTRUCT cs
return CView::PreCreateWindow(cs);
}
/////////////////////////////////////////////////////////////////////////////
// CSortView drawing
//функция вывода данных на экран
void CSortView::OnDraw(CDC* pDC)
{
CSortDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
// TODO: add draw code for native data here
int i;
//выводим исходный массив на экран
for(i=0;i
{
str.Format("%d,",mas[i]);//формирование строки
pDC->TextOut(10+i*20,10,str);//выводна экран
}
//если был выбран какой-нибудь метод сортировки
if(sort)
{
if(metod==1)//если выбран Quicksort
pDC->TextOut(10,40,«Обменная сортировка с разделением (quicksort)»);//вывод строки на экран
if(metod==2)//если выбран Shell
pDC->TextOut(10,40,«МетодШелла»);//вывод строки на экран
if(metod==3)//если выбран Bubble
pDC->TextOut(10,40,«Метод прямого обмена(Пузырька)»);//вывод строки на экран
//выводим отсортированный массив
for(i=0;i
{
str.Format("%d,",mas2[i]);//формирование строки
pDC->TextOut(10+i*20,80,str);//выводстроки на экран
}
str.Format(«Количество перестановок внашем случае: %d»,count);//формирование строки
pDC->TextOut(10,110,str);//вывод строки на экран
if(metod==3)//если был выбран метод«Пузырька»
{
str.Format(«Максимальное количествоперестановок для массива из %dэлементов методом 'Пузырька': %d»,kol, kol*(kol-1)/2);//формированиестроки
pDC->TextOut(10,140,str);//вывод строки на экран
}
}
}
/////////////////////////////////////////////////////////////////////////////
// CSortView diagnostics
#ifdef _DEBUG
void CSortView::AssertValid() const
{
CView::AssertValid();
}
void CSortView::Dump(CDumpContext& dc) const
{
CView::Dump(dc);
}
CSortDoc* CSortView::GetDocument() // non-debug version isinline
{
ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CSortDoc)));
return (CSortDoc*)m_pDocument;
}
#endif //_DEBUG
/////////////////////////////////////////////////////////////////////////////
// CSortView message handlers
//при выборе сортировки Quicksort
void CSortView::OnQuick()
{
//объявление локальных переменных
sort=true;
metod=1;
int i;
count=0;
for(i=0;i
{
mas2[i]=mas[i];
}
quicksort(0, kol-1);//вызов функции quicksort
Invalidate(true);//перерисовкасодержимого окна
}
//при выборе сортировки Shell
void CSortView::OnShell()
{
//объявление локальных переменных
sort=true;
metod=2;
int ii,t=5,i,j, k, s, m, h[6], x;
count=0;
for(ii=0;ii
{
mas2[ii]=mas[ii];
}
h[1]=9; h[2]=5; h[3]=3; h[4]=2; h[5]=1;
////////////////////////////////////////////
//АЛГОРИТМ
for(m=1;m
{
k=h[m];
s=-k;
for(i=k+1; i
{
x=mas2[i];
j=i-k;
while (x
{
mas2[j+k]=mas2[j];
j=j-k;
}
mas2[j+k]=x;
count++;
}
}
x=mas2[0];
mas2[0]=mas2[1];
mas2[1]=x;
////////////////////////////////////////////
Invalidate(true);//перерисовка содержимого окна
}
//при выборе сортировки Bubble
void CSortView::OnPuzirok()
{
//объявление локальных переменных
int dop;
bool end;
count=0;
sort=true;
metod=3;
int i, j;
for(i=0;i
{
mas2[i]=mas[i];
}
////////////////////////////////////////////
//АЛГОРИТМ
for(i=0;i
{
end=true;
for(j=i+1;j
{
if(mas2[i]>mas2[j])
{
dop=mas2[i];
mas2[i]=mas2[j];
mas2[j]=dop;
end=false;
count++;
}
}
if(end==true) break;
}
/////////////////////////////////////////////
Invalidate(true);//перерисовка содержимого окна
}
//функция быстрого поиска
void CSortView::quicksort(int l, int r)
{
int i, j;
i=l;j=r;
{
part(l, r, i, j);
if(i
if(j>l)quicksort(l, j);// переход к сортировке правой части
}
}
//функция поиска по частям
void CSortView::part(int l, int r, int &i, int &j)
{
int x, dop;
i=l;
j=r;
x=(l+r)/2;
do
{
while(mas2[i]
i++;
while(mas2[j]>mas2[x])
j--;
if(i
{
dop=mas2[i];
mas2[i]=mas2[j];
mas2[j]=dop;
i++;j--;count++;
}
}
while(i
}
Литература
1.Петзольд Ч. Программирование под Windows 95. В двух книгах: BHV – Санкт - Петербург, 1997, silt.
2. РичардС.Линкер, Том Арчер. Программирование для Windows 98. Библия разработчика. “Диалектика ” – Москва,1999.-864 с.: ил.- Парал. тит. англ. Уч.пос.
3. ДжессЛиберти. С++ за 21 день. ”Вильямс” — Москва, 2000.-816 с.: ил. - Парал.тит. англ.
4. Дэвид Дж.Круглински. Основы С++. “Русская редакция” – Москва, 1997.- 696 с.: ил.
5. КэйтГрегори. Использование Visual C++. “Вильямс” –Москва, 1999.-864 с.: ил… — Парал.тит. англ., уч. пос.
7. Конспектлекций.