Анализа методов сортировки одномерных массивов

Вставки в несколько  связанных списков

Идея метода основывается на предположении, что  ключи в исходном файле имеют  значения в некотором известном  диапазоне MAX и в этом диапазоне  они распределены довольно равномерно. Тогда по аналогии с методом вставки  в один связанный список можно  организовать несколько, например, Q списков. Величина Q зависит от ожидаемого среднего количес-тва элементов M в каждом списке то есть Q=N/M, N - количество ключей.

При разработке программы нужно проанализировать зависимость времени работы метода от параметра М для различных  исходных файлов и дать рекомендации по выбору оптимального значения.

Схема алгоритма  имеет следующий вид. Через Q обозначено количество списков, массив B[1]...B[Q] служит для хранения указателей на начала отдельных списков. Перед началом  работы алгоритма элементы массива В предполагаются равными 0. Каждый i-й элемент исходного файла содержит ключ K[i] и указатель L[i] на следующий элемент списка. Значение L[i]=0 соответствует последнему элементу в списке, указатель B[1] указывает на начало первого подсписка и одновременно на начало всего списка. Через minK обозначено минимальное значение ключа в файле, через М - среднее выбранное значение количества элементов в подсписке. d - номер текущего списка, в который должен быть вставлен элемент K[j]. Величина R=MAX/Q есть диапазон значений ключей, приходящийся на один список.

Время работы алгоритма t примерно оценивается формулой: t=a*NЅ + b*N

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Обменная сортировка

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

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

Метод пузырька

Алгоритм довольно очевиден.

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

Время работы алгоритма t примерно оценивается формулой: t=a*NЅ + b*N

где a,b - неизвестные константы, зависящие от программной реализа-

ции алгоритма.

Модификация метода пузырька

Модификация метода пузырька состоит в том, что файл можно просматривать как с  начала до конца, так и с конца  до начала попеременно. Это несколько  сокращает число перемещений  элементов.

Время работы алгоритма t примерно оценивается формулой: t=a*NЅ + b*N

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Быстрая сортировка.

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

Сортировка подфайлов, содержащих меньше чем М элементов, выполняется каким-либо простым методом, например простыми вставками. Таким образом, реализация метода зависит от двух параметров: значения М и способа выбора элемента, который предназначен для разделения файла на две части.

Блок выбора Х в простейшем случае формулируется  как X=K[l], однако это может привести к крайне неэффективному алгоритму. Наиболее простое лучшее решение - выбирать Х как случайный ключ из диапазона K[l] ... K[r] и обменять его с K[l].

Время работы алгоритма t примерно оценивается формулой:

t=a*N*logN + b*N

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Обменная поразрядная  сортировка

Данный метод  использует двоичное представление  ключей. Файл сортируется последовательно  по битам двоичного представления  ключей,начиная со старшего. Ключи, имеющие значение данного бита, равноенулю, ставятся в левую половину файла, а ключи со значением бита 1 в правую. Функция b(ключ) возвращает значение ьита с номером b аргумента, m -максимальное количество значащих битов в ключах.

Время работы алгоритма t примерно оценивается формулой:t=a*N*logN + b*N

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Параллельная  сортировка Бэтчера

Для получения  алгоритма обменной сортировки, время  работы которого меньше, чем NЅ, необходимо выбирать для сравнения и обмена ключи,расположенные возможно дальше друг от друга. Эта идея уже была реализована в алгоритме сортировки Шелла вставок с убывающим шагом, однако в данном алгоритме сравнения выполняются по-другому.

Время работы алгоритма t примерно оценивается формулой:t=a*N*(logN)Ѕ

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Сортировка посредством  выбора

Идея метода довольно проста: найти наибольший элемент файла и по-ставить его на место N, найти следующий максимум и поставить его на место N-1 и т.д. до 2-го элемента.

Время работы алгоритма t примерно оценивается формулой: t=a*NЅ+b*N* logN

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Использование связанного списка для хранения информации о проме-жуточных максимумах.

В алгоритме  максимум среди K[1] ... K[j-1] определяется в цикле от j-1 до 1 c целью обеспечить меньшее число обменов в случае равенства ключей и сохранении прежнего порядка равных элементов. Однако, если изменить порядок просмотра элементов на противоположный и изменить структуру данных, введя дополнительные указатели, можно пример-но в два раза сократить число повторений в цикле поиска максисмума. Каждый ключ K[i] снабжается указателем L[i] на элемент, максимальный среди первых i-1 элементов .

Тогда после  обмена элементов K[j] и K[m] поиск максимума  в следующем цикле по j можно  осуществлять среди элементов K[L[m]] ... K[j] при началь-ных значениях X=K[L[m]], m=L[m], т.к. максимум может "обновиться" только за счет элементов, лежащих правее локального максимума. Таким образом среднее количество просматриваемых при поиске максимума элементов со-кращается примерно в два раза.

Время работы алгоритма t примерно оценивается формулой:t=a*NЅ + b*N*logN

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Сортировка посредством  слияния

Алгоритмы сортировки этого класса основываются на объединении  нескольких (часто двух) уже упорядоченнх файлов. Рассмотренные далее алгоритмы выбирают из исходного файла упорядоченные отрезки и объединяют их в более длинные.

Естественное  двухпутевое слияние

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

Элементы файла  пересылаются из одной области в  другую, меняя направление пересылки. Для запоминания направления  пересылки служит переменная s, принимающая  значения TRUE и FALSE попеременно. Другой логический признак f служит сигналом продолжения-окончания алгоритма, если все области слились в конце концов в одну. Переменная d принимает попеременно значения +1 -1 и указывает направление просмотра файла: вперед или назад.Операция <-> обозначает обмен значениями двух переменных. Операция Џ обозначает инверсию логической переменной или выражения.

Время работы алгоритма t примерно оценивается формулой:

t=a*N*lgN + b*N

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

Простое двухпутевое слияние.

В алгоритме  естественного двухпутевого слияния упорядоченный отрезки файла определялись случайным расположением элементов в исходном файле. В данном алгоритме длина отрезков фиксируется на каждом шаге. В исходной файле все отрезки имеют длину 1, после первого шага она равна 2, после второго 4, после третьего - 8, после к-го шага -2 в степени к.

Время работы алгоритма t примерно оценивается формулой: t=a*N*lgN + b*N

где a,b - неизвестные константы, зависящие от программной реализации алгоритма.

1.2 ОБОСНОВАНИЕ  ВЫБОРА МЕТОДА РЕШЕНИЯ ЗАДАЧИ 

Сортировка массива  быстрым методом является прекрасным примером целесооразности использования рекурсивного обращения в программированние на языке Си . Метод быстрой сортировки был предложен К. А. Р. Хоором в 1962г. Предложенная версия быстрой сортировки , разумеется , не самая быстрая среди всех возможных ,но зато она из самых простых .

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

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

3.  
РАЗРАБОТКА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

Алгоритм решения  задачи предельно прост. Функция  main() явлвется функцией меню и выполняет опрос клавиатуры . В зависимости от нажатой клавиши выполняет соответствующие действия программы. Для чтения информации о программе из файла text.hlp используется функция help(), которая работает с файловым выводом. Функция file() основная так как с её помощью выполняется сортировка массива (вызов функций qqsort() и srecmg()) определение времени сортировки вызов функции построение гистограмм. Массив состоит из случайных чисел вводимых в него функцией генератора случайных чисел. Далее функция file() вызывает соответствующие функции сортировки, засекает время сортировки соответствующим способом , и заносит это время в массив simvol[]. Далее данные из массива передаются в функцию grafix(), где они используются при выводе на экран гистограмм в графическом режиме . Программа предусматривает случаи отсутствия некоторых программных элементов. В этом случае вызывается функция Error(), которая создаёт окно сообщения в которое вписываются характеристика ошибки. Так программа не будет выполнятся если не найден файл “text.hlp” или драйвер EGAVGA.BGI

.  3. РАЗРАБОТКА  ПРОГРАММЫ

3.1 ОПИСАНИЕ  ПРОГРАММЫ

Данная программа  называется “TEST” (имя исполняемого файла test.exe) и предназначена для  анализа методов сортировки одномерного  массива. Программа работает на IBM совместимых компьютерах семейства х86 начиная с 286 и выше, в операционной системе типа Ms-DOS 3.0 и выше.

Программа содержит пять основных функций: main(), file(), qsort(), srecmg(), grafix(). Все переменные, используемые в программе являются локальными.

Функция main() содержит пункты меню и вызывает другие исполняемые функции в зависимости от нажатия предложеных функциональных клавиш F1, F2 и F10. Каждая из этих функций работает автономно и независимо от двух других.

Программа реализована  как в псевдографическом так и в графическом режиме (в связи с чем она может компилироваться только в DOSовских версиях BorlandC++ или BorlandC). В графическом режиме она выводит на экран гистограмму которая характеризует время сортировки массивов двумя способами.

Программа использует как стандартный так и файловый ввод-вывод информации . Стандартный ввод представлен запросом программы на ввод функциональных клавиш , которые задают характер выполняемого действия . Файловый ввод-вывод используется в функции help(), для вывода на экран информации о разработчике программы , её функциональных клавишах и о возможных ошибках в процессе выполнения. Кроме того программа работает с функцией времени clock() и переменными времени типа clock_t.