Курсовая работа: Анализ методов сортировки одномерного массива

printf() – эта функция осуществляет вывод строки на экран.

fopen() – эта функция открывает файл с заданным именем и возвращает поток или NULL, если попытка открытия оказалась неудачной .

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

fgetc() – эта функция возвращает следущуюлитеру из потока stream в виде unsignedchar или EOF, если исчерпан файл или обнаружена ошибка .

puts() – пишет стринг s и литеру новая – строка в stdout . Возвращает EOF в случае ошибки , или неотрицательное значение , если запись прошла нормально .

Из библиотеки <conio.h>

textbackground() – с помощью этой функции устанавливается цвет фона для функции cprintf().

textcolor() – с помощью этой функции устанавливается цвет текста для функции cprintf().

clrscr() – функция очистки экрана, цветом установленным функцией textbackground().

cprintf() – с помощью этой функции осуществляется вывод строки с учётом цветов установленных функциями textbackground(), textcolor().

_setcursortype() – с помощью данной функции осуществляется изменение режима отображения курсора. Данных режимов в Си всего три – NOCURSOR (курсор выключен), SOLIDCURSOR (курсор в виде сплошного блока) NORMALCURSOR (обычный курсор).

getch() – функция getch осуществляет считывание первого единственного символа с клавиатуры, используется при считывании клавиш курсора при перемещении по окну выбора режима работы программы.

gotoxy() – эта функция перемещает курсор в нужную часть экрана, обычно используется перед функцией cprintf().

В этой библиотеке описаны все символические константы цветов используемые функциями textbackground(), textcolor(). В ней также описаны все типы курсоров используемых функцией _setcursortype().

3.1.1 ОПИСАНИЕ ФУНКЦИИ main()

Функция main имеет тип void и является функцией меню. Main выполняет опрос клавиатуры и в зависимости от нажатой функциональной клавиши выполняется соответствующее действие (вызов помощи , тестирования и выход из программы). Эта возможность реализована благодаря конструкции множественного выбора switch . Функция имеет одну локальную переменную press имеющую тип char . Она воспринимает символ с клавиатуры без вывода на экран и используется в конструкции switch при переходе к другой выполняемой функции . В данной функции вызывается вспомогательная функция windows() , которая создаёт псевдографический интерфейс при запуске программы. При выборе пункта выхода из программы стандартная функция textbackground() создаёт черный экран ,а функция exit() совершает выход из программы.

При вызове функции помощи (help()) программа обращается к этой функции, которая считывает и выводит информацию файловым способом. Вызываемый фаил хранится под именем test.hlp и при его отсутствии выдаётся окно сообщения : «Фаил text.hlp не найден».

Вызов функции построения гистограмм выполняется при нажатии клавиши F2. При этом функция main() обращается к функции file() .

3.1.2 ОПИСАНИЕ ФУНКЦИИ srecmg().

Для построения упорядоченного списка В’ из списка В=<к1,к2,...,кn> при сортировке слиянием список В делится на n подсписков В1=<к1>, В2=<к2> , ... , Вn=<кn> длины 1. Потом совершается процедура прохождения в которой m≥2 упорядоченных списков В1,В2,...,Вm меняются на m/2 ( или (m+1)/2) упорядоченных списков которые создаются слиянием B2i-1и B2i (2i≤m) и суммированием Bmc непарным m. Процесс повторяется до появления одной последовательности длины m. Количество действий , необходимых для сортировки слиянием , равна nlog2n, потому что за одно прохождение выполняется n сравнений , а всего необходимо осуществить log2n прохождений . Сортировка слияниием дастаточно эффективно и используется при больших значения n.

Функция srecmg() является рекурсивной , и сортирует массив а[n]. За каждым вызовом массив для сортировки делится на две части – от а[0] до

a[i-1] и от a[i] до a[n] , каждая из которых сортируется отдельно , а потом выполняется их слияние. Слияние выполняется при помощи вызываемой функции merge() в которую передаётся указатель на массив , текущий номер элемента массива и количество элементов массива . Параметрами функции merge() являются массив w[ ] ,его длина l/2 и длина первой части массива l1 .Функция merge() выполняет слияние подмассивов , образуя на их месте упорядоченный массив w[0],w[1],...,w[l2-2],w[l2-1] .

3.1.3 ОПИСАНИЕ ФУНКЦИИ qqsort()

Быстрая сортировка состоит в том , что список В=<k1,k2,…,kn> реорганизуется в B’,<k1>,B”,где В’ – подсписок В с элементами , не большими k1 , а B” – подсписок В с элементами большими k1. В списке В’,<k1>,В” элемент К1 уже находится на месте где он должен быть в отсортированом списке. Дальше к спискам В’ и В’’ применяется упорядованичение быстрой сортировкой .

Рекурсивная функция qqsort упорядоваечет быстрой сортировкой участок масcива целых чисел первый элемент которого указывается показателем v[left] , последний – показателем v[right].

Если участок масива более чем из двух элементов , v[left] – low >1,то находится делящий элемент и переносится в V[0]. Пременной last присваивается значение первого элемента массива left. Затем массив делится на две части, элементы которых соответственно больше и меньше last. Далее функция выполняет перезапоминание делящего элемента и вызывает себя для разбитых подсписков .

Обмен элементов выполняется при помощи функции swap() , в которую из функции qqsort() перелаётся указатель на массив и элементы , место-положение которых в массиве нужно обратить .

Время построения списка зависит от его начального состояния. Время будет минимальным , если каждый шаг раздела дает подсписки В’ , B’’ приблизительно одинаковой длины ; тогда необходимо (nlog2 n) шагов . Если начальный список мало чем отличается от обычного отсортированного то необходимо (n^2)/2 шагов . Быстрая сортировка требует дополнительной памяти порядка O (log2n) для исполнения рекурсивной функции qqsort() (неявного стэка).

3.1.4 ОПИСАНИЕ ФУНКЦИИ grafix()

Функция grafix() имеет тип void и параметр simbol[2] – массив скорости выполнения сортировки . Эта функция вызывается при построении гистограммы и работает в графическом режиме о чем информирует строка initgraph(&gdriver, &gmode, ""), которая устанавливает систему в графический режим , определяет характеристику видеодрайвера. Если переменная errorcode не получает значение grOk , то дальнейшее выполнение программы не возможно так как графический режим не установлен (о чем выводится сообщение). В массиве simvol[] определяется больший элемент , столбец которого устанавливается в 100% .