1 часть курсовой работы "Методы сортировки"

Для проведения исследования были выбраны следующие алгоритмы сортировки:

Insertion sort

Сортировка включением – алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получим отсортированный массив. Сложность данного алгоритма равна O(n^2).

Selection sort

Сортировка выбором – суть алгоритма заключается в проходе по массиву от начала до конца в поиске минимального элемента массива и перемещении его в начало. Сложность такого алгоритма O(n2).

Bubble sort

Сортировка пузырьком– данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность данного алгоритма сортировки равна O(n^2).

Было проведено 9 опытов (3 метода х 3 реализации одномерного массива), в каждом из которых определено два числа (С - Количество сравнений М - Количество перемещений), но в третьем случае, случайного массива, в отличие от двух первых, сравнительный анализ алгоритмов возможен только по средним значениям.

Исходя из проделанной работы можно сделать вывод. Самым эффективным методом сортировки для массива является метод "Select"

Оставить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *