· Метод Шелла.
Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами. Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.
При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако, он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.
Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 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 < n <= 2**(k+1).
После выбора h1 методом вставки упорядочиваются группы, содержащие элементы с номерами позиций
i, i+h1, i+2*h1, ..., i+mi*h1.
При этом i=1,2,...,h1; m[i] - наибольшее целое, удовлетворяющее неравенству i+m[i]*hi <= n.
Затем выбирается шаг h2<h1 и упорядочиваются группы, содержащие элементы с номерами позиций i, i+h2, ..., i+m[i]*h2. Эта процедура со все уменьшающимися шагами продолжается до тех пор, пока очередной шаг h[l] станет равным единице (h1>h2>...>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<j.
Каждый раз массив разбивается на два подмассива, один из которых обрабатывается, в то время как границы второго запоминаются с тем, чтобы он был обработан позже. В этих целях может быть использован стек, представляющий собой матрицу из двух столбцов. В первом столбце хранятся нижние границы разделяемых подмассивов, во втором - верхние границы. Всякий раз один из полученных в результате разделения подмассивов подвергается дальнейшему разделению, а границы другого помещаются в свободную строку стека (обычно в стек помещаются границы большего по длине массива, поскольку это уменьшает требуемый размер стека). Как только завершается процесс разделения текущего подмассива, т.е. ее длина станет меньше трех, для разделения берется подмассив, границы которого были занесены в стек последними. Строка стека, в которой хранились эти границы, освобождается. Процесс упорядочения завершается, когда стек полностью освобождается.
Разделение следует применять для подмассивов, длина которых больше 9, а короткие подмассивы упорядочивать методом вставки.
Стек занимает мало места. Например, стек из 20 строк позволяет упорядочить массив, содержащую до 10**7 записей. Кроме того, в современных языках программирования при работе рекурсивных программ занесение и извлечение из стека выполняется автоматически, поэтому рекомендуется использовать именно этот механизм. Среднее число сравнений для данного алгоритма составляет n*log(n) где n - число записей в сортируемом массиве, m - размер подмассива, сортируемой методом вставки.
Наихудшей ситуацией при использовании рассмотренного алгоритма является случай, когда массив уже отсортирован. При этом число сравнений порядка n, т.е. алгоритм не лучше сортировки выборкой.
2.2 Описание программы “Sort”
Данный проект создавался с помощью AppWizard – генератором кода, создающим рабочую заготовку Windows-приложения с теми компонентами, именами классов и исходными файлами, что были указаны через диалоговые окна. В частности: в закладке Project выбираем - MFCAppWizard (exe). Затем нужно пройти серию экранов AppWizard:
Step 1: выбираем “Single document”
Step 2: оставляем без изменения
Step 3: без изменения
Step 4: оставляемтолькофлажки “3D controls”, “Docking ToolBar”
Step 5: устанавливаем “As a statically linked library”
Step 6: отображает информацию о созданных классах
После этого AppWizard сгенерирует код для поддержки функциональных возможностей программы на базе библиотеки MFC, т.е. создаст каркас приложения. Рассмотрим некоторые элементы программы, созданные на данном этапе:
Класс CSortApp. Объект класса CSortApp представляет программу. В программе определяется единственный глобальный объект класса CSortApp – theApp. Базовый класс CWinApp определяет основные характеристики объекта theApp.
Класс CSortView. Объект класса CSortView представляет основное окно программы. Когда конструктор вызывает функцию-член Create базового класса CFrameWnd, Windows создаёт действительную оконную структуру, а каркас приложения связывает её с C++-объектом. Функции ShowWindow и UpdateWindow, являющиеся также функциями-членами базового класса, вызываются для вывода окна на экран.
При запуске проекта операционная система вызывает в программе функцию WinMain, а та ищет глобально сконструированный объект класса, производного от CWinApp. В любом приложении, в том числе и в “Sort”, обязательно должна присутствовать эта функция, на которую возлагается ряд специфических задач. И самая важная – создание основного окна программы, с которым должен быть связан код, способный обрабатывать сообщения, передаваемые операционной системой этому окну. В нашем случае при программировании на MicrosoftVisualC++ 6.0, с библиотекой классов MicrosoftFoundationClass (MFC) Library 6.0, эта функция скрыта внутри каркаса приложения и нет необходимости в её написании, но необходимо понимать, что именно с помощью неё осуществляется связь между операционной системой и программой.
Библиотека MFC прямо поддерживает около 140 функций, обрабатывающих Windows-сообщения. Кроме того, можно определять свои собственные сообщения, связанные с обработчиками команд меню, элементов управления и т.д. В программе “Sort” используется более 40 функций, методов и сообщений Windows. Ниже они перечислены в порядке их появления в программе с кратким описанием: