Содержание
Сортировка одномерного массива
В программе реализованы два алгоритма сортировки массива: и быстрая сортировка Хоара и битоническая сортировка.
Быстрая сортировка
Общая идея алгоритма состоит в следующем:
Выбрать из массива элемент, называемый опорным. Это может быть любой из элементов массива или же число, вычисленное на основе значений элементов. На практике обычно выбирается средний элемент массива.
Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующие друг за другом: «меньшие опорного», «равные» и «большие».
Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.
Листинг кода
#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];
Выдержка из текста
В ходе данной лабораторной был изучены алгоритмы сортировки (битоническая и быстрая сортировка Хоара). Была сделана программная реализация данных алгоритмов. Для данной программной реализации были проведены ряд тестов, показывающие правильность работы алгоритмов сортировки.
Была проделана реализация работы с матрицами, а именно: вычисление детерминанта, произведения матриц и нахождение обратной матрицы. Были представлены тестовые примеры, подтверждающие правильность работы программы, а так же разобран ряд критических случаев.
Список использованной литературы
.
С этим материалом также изучают
Детальное руководство по написанию курсовой работы по алгоритмам и структурам данных для студентов. В статье вы найдете подробный разбор структуры, примеры кода на C++, анализ сложности алгоритмов и советы по оформлению.
Разбираем все этапы создания курсовой работы по алгоритмам и структурам данных. Внутри вы найдете детальный анализ двунаправленных списков, объяснение сортировки пузырьком, примеры кода на С и советы по оформлению.
... Задача: Сквозная сортировка матрицы A[m,n] по столбцам по неубыванию. Метод: Прямой обмен. Способы обхода: 1.Переписать элементы исходного массива в дополнительный одномерный массив. Выполнить сортировку. Возвратить ...
... 3.2 Сортировка выбором 21 3.3 Сортировка включением 23 3.4 Оценка алгоритмов сортировки 25 4 УСОВЕРШЕНСТВОВАННЫЕ АЛГОРИТМЫ СОРТИРОВКИ 27 4.1 Турнирная сортировка 27 4.2 Сортировка Шелла 29 4.3 Быстрая сортировка Хоара 31 ...
... массива.Составить алгоритмы сортировки или поиска в многомерном массиве заданными методами, согласно варианту.Выполнить сортировку, делая обход непосредственно по элементам исходного массива, не используя дополнительного массива и преобразований ...
... с16.Андреева Т. А. Лекция №4.2: Сортировки массивов – 2008 URL: http://pascal.toom.su/%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D0%B8 (дата обращения: 22.02.2012).17.Быстрицкий В.Д. Сравнение алгоритмов сортировки массивов.// ALGLIB [Электронный ресурс]. URL: ...
... массиве 131.5. Бинарный поиск в упорядоченном массиве 131.6. Интерполяционный поиск элемента в массиве 152. Алгоритм оценки эффективности методов сортировки ... того, какие алгоритмы будут к ним применяться, и наоборот, выбор алгоритма часто очень ...
... URL: http://www.comprog.ru/PascalDelphi/article_4191.htm21.Быстрицкий В.Д. Сравнение алгоритмов сортировки массивов.// ALGLIB [Электронный ресурс ... комплексный алгоритм (в надежде, что результирующая программа будет выполняться существенно быстрее). ...
... ……………………………………….. 7 4. Анализ сортировки методом Шелла………………………………. 16 5. Алгоритм быстрой сортировки…………………………………….. 17 6. Характеристики производительности быстрой сортировки……… 23 7. Методы улучшения быстрой сортировки…………………………. 24 7.1 Небольшие ...
