Содержание
Сортировка одномерного массива
В программе реализованы два алгоритма сортировки массива: и быстрая сортировка Хоара и битоническая сортировка.
Быстрая сортировка
Общая идея алгоритма состоит в следующем:
Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива или же число, вычисленное на основе значений элементов. На практике обычно выбирается средний элемент массива.
Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».
Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
Листинг кода
#include "Header.hpp"
/****************************************************
Быстрая сортировка Хоара
*data — массив элементов
left — номер первого элемента сортируемого массива
right — номер последнего элемента сортируемого массива
*****************************************************/
void quickSort(double *data, int left, int right)
{
int left1 = left;
int right1 = right;
double p;
double ref = data[(left+right)/2];
Выдержка из текста
В ходе данной лабораторной был изучены алгоритмы сортировки (битоническая и быстрая сортировка Хоара). Была сделана программная реализация данных алгоритмов. Для данной программной реализации были проведены ряд тестов, показывающие правильность работы алгоритмов сортировки.
Была проделана реализация работы с матрицами, а именно: вычисление детерминанта, произведения матриц и нахождение обратной матрицы. Были представлены тестовые примеры, подтверждающие правильность работы программы, а так же разобран ряд критических случаев.
Список использованной литературы
.