Анализ некоторых видов сортировок
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
µся выделением памяти, контроль процесса выполнения программы, преобразования типов и другие. Заголовок вполне совместим с C++ и известен в нём как cstdlib. Название stdlib расшифровывается как standard library (стандартная библиотека).
(от англ. standard input/output header - стандартный заголовочный файл ввода/вывода) заголовочный файл стандартной библиотеки языка Си, содержащий определения макросов, константы и объявления функций и типов, используемых для различных операций стандартного ввода и вывода. Функциональность унаследована от портативного пакета ввода/вывода (portable I/O package), написанного Майком Леском из Bell Labs в начале 1970-х. C++ ради совместимости, также использует stdio.h наряду со схожим по функциональности заголовочным файлом cstdio.
(от англ. console input-output - консольный ввод-вывод) - заголовочный файл, используемый в старых компиляторах, работающих в операционных системах MS-DOS.Этот заголовочный файл объявляет несколько библиотечных функций для работы с консольным вводом и выводом программы
- заголовочный файл стандартной библиотеки языка Си, содержащий функции для работы с нуль-терминированными строками и различными функциями работы с памятью.Функции объявленные в string.h широко используются, так как являясь частью стандартной библиотеки, они гарантированно работают на всех платформах, поддерживающих Си. Кроме этого, строковые функции работают только с набором символов ASCII или его совместимыми расширениями, такими как ISO-8859-1; многобайтовые кодировки такие как UTF-8 будут работать, с отличием, что длина строки будет определяться как число байтов, а не число символов Юникода, которым они соответствуют
- стандартная библиотека С++ подключающая графический режим.
Стандартные типы данных:
В данной программе используются следующие стандартные переменные:
int целочисленный знаковый тип данных, диапозон от -32768…32767. Размер 1 байт
long int целочисленный знаковый тип данных,диапозон от 2147483648…2147468647.Размер 4 байта.
char символьный тип данных, предназначенный для хранения одного символа в определённой кодировке. Если char определён как signed (знаковый), то его диапазон значений составляет от ?127 до 127 (на единицу больше в положительную или отрицательную сторону, в зависимости от реализации). Если он определён как unsigned (беззнаковый), то его значения могут составлять от 0 до 255. Значение, содержащееся в этом типе, можно всегда безопасно привести к значению типа int. В Си нет примитивных типов для работы со строками, поэтому для работы с ними используется указатель char *.
double вещественный тип данных с плавающей точкой и двойной точностью.Диапозон 1,7е-308…1,7е+308.Размер 8 байт.
struct time t;(&t);(Еру current time is: :d:d:d\n, t.ti_hour, t.ti_min, t.ti_sec , t.ti_hund, )
Данная структура выводит время в которое была вызвана данная функция.
t.ti_hour - поле структуры выводящее часы.
t.ti_min - поле структуры выводящее минуты.
t.ti_sec - поле структуры выводящее секунды.
t.ti_hund - поле структуры выводящее миллисекунды.
Описание собственных функций,которые используются в программе
SORTI.CPP-модуль,в котором находятся подпрограммы 4-х сортировок, подпрограммы выводящие время начала сортировки и время конца сортировки и общее время сортировки,подпрограмма генерирование массива(случайным образом,по убыванию и по возрастанию)
FILI.CPP- модуль в котором находятся подпрограммы записи данных на внешнюю память.
void puzir(int*& kop,int razmer) - даннай функций сортирует переданный массив методом пузырька.
Пример работы алгоритма:
Возьмём массив с числами 5 1 4 2 8 и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Первый проход:
(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.
(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5 > 4
(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5 > 2
(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах
(8 > 5), алгоритм не меняет их местами.
Второй проход:
(1 4 2 5 8) (1 4 2 5 8)
(1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4 > 2
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было.
Третий проход:
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)
(1 2 4 5 8) (1 2 4 5 8)Теперь массив отсортирован и алгоритм может быть завершён.
void protalkivanie(int*& kop,int razmer) - функция сортирующая массив методом выбора.
Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.
Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.
На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.
Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.
void vstavka(int*& kop,int razmer) - функция сортирующая массив методом вставки.
Сортировка простыми вставками в чем-то похожа на вы