Программирование на C++ — выбрать тему из списка

Целью курсовой работы является закрепление основ и углубление знаний в области структур и алгоритмов обработки данных в ЭВМ.

При сравнении числовых ключей алгоритм выполняет сортировку быстрее, по сравнению со строковыми данными, также некоторые алгоритмы сортирует массив быстрее если он имеет меньший объем записи. Поэтому перед выбором алгоритма необходимо учитывать начальные характеристики записей в таблице, чтобы минимизировать число выполняемых операций.
Также следует учитывать сложность реализации алгоритма. Для использования совсем простого алгоритма требуется меньше времени и ресурсов, а также вероятность ошибки минимально. Но простые алгоритмы могут иметь меньшую эффективность функционирования. Но при изготовлении программы из-за требования сроков разработки, а также надежность разрабатываемого продукта иногда лучше всего применять именно простые алгоритмы.
Так как алгоритмов сортировки очень много их классифицировали по логическому характеристикам. Каждый алгоритм использует одну из четырех стратегий:
Выборка. Изначального множество выбирается элемент, который должен следовать следующим по критерию упорядоченности, и помещается отсортировать массив на место, которое следует номеру.
Включение. Из изначального массива выбирается следующий по номеру элемента и помещается в отсортированный массив на то место которое он должен занимать.
Распределение. Исходный массив разделяется на несколько подмножеств таким образом происходит сортировка каждого подмножества.
Слияние. Отсортированный массив появляется с помощью слияния маленьких упорядоченных подмножеств.
Несколько известных сортировок:
«Дилетантская» сортировка. В основе лежит логика здравого смысла. Необходимо переставлять элементы массива, если они нарушают порядок, количество таких перестановок должно соответствовать количеству возможных пар элементов, а это дает цикл в цикле. Принцип сравнения «каждый с каждым» приводит к тому, что для каждого i-го элемента необходимо просмотреть все последующие за ним (второй цикл начинается с j=i). И наконец, программа отражает справедливую убежденность большинства, что за один цикл просмотра упорядочить массив нельзя. Парадокс: несмотря на явное наличие обмена, эта сортировка относится к группе сортировок выбором.
Проверка упорядоченности. Функция проверки упорядоченности массива является живой иллюстрацией теоремы: массив упорядочен, если упорядочена любая пара соседних элементов.
Сортировка выбором. На каждом шаге сортировки из последовательности выбирается минимальный элемент и переносится в конец выходной последовательности. Дальше вступают в силу детали процесса, но характерным остается наличие двух независимых частей – неупорядоченной (оставшихся элементов) и упорядоченной. При исключении выбранного элемента из массива на его место может быть записано «очень большое число», исключающее его повторный выбор. Выбранный элемент может удаляться путем сдвига оставшейся части, минимальный элемент может меняться местами с очередным.
Сортировка вставками. Основная идея алгоритма: имеется упорядоченная часть, в которую очередной элемент помещается так, что упорядоченность сохраняется (включение с сохранением порядка). Технические детали: можно проводить линейный поиск от начала упорядоченной части до первого большего, чем включаемый, использовать двоичный поиск места в упорядоченной части. Сама процедура вставки включает в себя перемещение элементов массива. В следующем примере последовательность действий по вставке очередного элемента в упорядоченную часть «разложена по полочкам» в виде последовательности четырех действий, связанных переменными (извлечение, поиск места, сдвиг, вставка).
Вставка погружением. Очередной элемент «погружается» путем ряда обменов с предыдущим до требуемой позиции в уже упорядоченную часть массива, пока «не достигнет дна», либо пока не встретит элемент, меньший себя. Наличие контекста «трех стаканов» делает его подозрительно похожим на обменную сортировку, но это не так.
Сортировка Шелла. Существенными в сортировках вставками (или обмена) являются затраты на обмены или сдвиги элементов. Для их уменьшения желательно сначала производить погружение с большим шагом, сразу определяя элемент «по месту», а затем делать точную «подгонку». Так поступает сортировка Шелла: исходный массив разбивается на m частей, в каждую из которых попадают элементы с шагом m, начиная от 0,1,...,m-1 соответственно.
Сортировка Шелла требует четырех вложенных циклов: по шагу сортировки (по уменьшающимся степеням 2 – m=64,32,16…), по группам – (по индексу первого элемента в диапазоне k=0…s-1), а затем два цикла обычной сортировки погружением для элементов группы, начинающейся с k с шагом m.
Обменная сортировка представляет собой самое прямолинейное решение проблемы: если в упорядоченной последовательности все пары соседних элементов упорядочены, то нужно достаточно долго переставлять «неправильные» пары, пока порядок не установится. Как мы уже знаем, для этого достаточно двойного цикла. Первая оптимизация состоит в том, что сортировку можно прекратить, если при просмотре всех пар от начала да конца перестановок не будет.
Обменные сортировки имеют ряд особенностей. Прежде всего, они чувствительны к степени исходной упорядоченности массива. Полностью упорядоченный массив будет просмотрен один раз, в то время как выбор или вставка будут «изображать бурную деятельность». Кроме того, имеется несколько свойств, на котором основана их оптимизация. Они непосредственно не наблюдаемы в тексте программы, ему не соответствуют никакие программные контексты, и они выводятся только «историческим» анализом программы.
Сортировки рекурсивным разделением. Сортировки разделяют массив на две части относительно некоторого значения, называемого медианой. Медианой может быть выбрано любое «среднее» значение, например, среднее арифметическое. Сами части не упорядочены, но обладают таким свойством, что элементы в левой части меньше медианы, а элементы правой - больше. Благодаря такому свойству эти части можно сортировать независимо. Для этого нужно вызвать ту же самую функцию сортировки, но уже не по отношению к массиву, а к его частям. Функции, вызывающие сами себя, называются рекурсивными.
Рекурсивный вызов продолжается до тех пор, пока очередная часть массива не станет содержать единственный элемент. Так будет выглядеть «заготовка» сортировки разделением, использующая простейший способ реализации разделения.
Сортированные массивы с бинарным поиском являются очень неэффективным решением, когда операции вставки и удаления чередуются с извлечением, принимая O ( N ). Время для каждой такой операции и усложняет использование памяти. Другие структуры данных поддерживают гораздо более эффективную вставку и удаление, а также быстрое точное соответствие. Однако двоичный поиск применяется к широкому кругу проблем поиска, обычно решая их в O. Независимо от типа или структуры самих значений.

Используя бинарный и линейный поиск – мы смогли понять, какой из них является наиболее эффективным. В работе была приведена программная реализация данных алгоритмов, для каждого алгоритма был создан свой отдельный метод, позволяющий найти значений в массиве. Также, с целью универсальности и эргономичности – были введены такие классы как параметры алгоритма и шаблонный массив.
Параметры алгоритма могут замеряться не только на поиске – благодаря продуманной универсальности, их можно подставить в любую другую программу, после чего замерить параметры, скажем, создания вектора большой длины, или время построения графика.
Вместе с тем шаблонный массив позволяет упростить задачу поиска – так, мы сможем проверить поиск на различных типах элементах, и экспериментально доказать, что на типах с большей размерностью поиск менее эффективен чем на типах с меньшей размерностью. Все, что необходимо сделать для создани такого массива – так это задать его тип и размер.
Шаблонный массив имеет встроенную сортировку Хоара, что позволяет использовать бинарный поиск с наименьшей потерей эффективности.
Резюмируя – была создана программа, позволяющая наглядно просмотреть работу линейного и бинарного поиска, выполненная в ООП стиле и позволяющая программисту дополнить и усовершенствовать ее.