Эмпирический анализ и исследование производительности для каждого алгоритма в отдельности. Оценка количества сравнений, обменов и времени работы алгоритма.
Отчет о выполнении лабораторной работы №1 на тему: «Алгоритмы сортировки. Анализ производительности и визуализация» по курсу «Алгоритмы и анализ сложности»
Днепропетровск Содержание 1. Постановка задачи. 2. Псевдокод алгоритмов. 3. Эмпирический анализ и исследование производительности для каждого алгоритма в отдельности. Оценка количества сравнений, обменов и времени работы алгоритма. 4.Сравнение производительностей алгоритмов для массивов из 5. Графическое представление полученных данных, вывод на основе их о принадлежности алгоритмов к классам.
Постановка задачи. Рассмотреть 2 группы алгоритмов сортировки – элементарные и более эффективные алгоритмы сортировки. Выполнить их анализ. Мною рассматриваются следующие элементарные алгоритмы: сортировка выбором(selection sort) и простая сортировка вставкой(straight insertion sort) и более эффективные – алгоритм сортировки слиянием(merge sort) и быстрая сортировка(quick sort). Псевдокод алгоритмов. Вход: массив A, состоящий из элементов A[0], A[1],..., A[n-1] Выход: отсортированный массив. · сортировка выбором Описание: Алгоритм находит в массиве минимальный элемент и меняет его местами с первым элементом. Далее алгоритм повторяет эти два действия для еще не отсортированной части массива, пока массив не закончится.
for i =0,1,…,n-2 begin min = i
for j = i + 1, i+2,…,n-1 if A[j] < A[min] then min = j
if A[min]!=A[i] then Swap(A[i], A[min]) endfor
· простая сортировка вставкой Описание: Рассматриваются массивы размером 2, 3,…, n элементов и в них поочередно сравниваются два соседних элемента
for i = 1,2,…,n-1 begin j = i while j > 0 and A[j - 1] > A[j] begin Swap(A[j], A[j-1]) j=j-1 endwhile
endfor
· сортировка слиянием Описание: Сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе.
function Merge_Sort(A, n) begin mid_point = n / 2 return Merge(Merge_Sort(A.Take(mid_point), n), Merge_Sort(A.Skip(mid_point), n), n) end
function Merge(mass1, mass2, n) begin a = 0, b = 0 int[] merged = new int[mass1.Length + mass2.Length] for i = 0, 1,…, mass1.Length + mass2.Length-1 begin if b < mass2.Length and a < mass1.Length then begin if mass1[a] > mass2[b] and b < mass2.Length then begin b:=b+1 merged[i]:= mass2[b] endthen else begin a:= a+1 merged[i]:= mass1[a] endelse endthen else if b < mass2.Length then begin b:=b+1 merged[i]:= mass2[b] endthen else begin a:= a+1 merged[i]:= mass1[a] endelse endfor return merged endfunction
· быстрая сортировка Описание: Выбираем элемент, называемый опорным, сравниваем все остальные элементы с опорным. На основании сравнения разбиваем множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие -равные -большие. Повторяем рекурсивно для «меньших» и «больших».
function qSort(A, low, high) begin i = low j = high x = A[(low + (high-low)/2)] do begin while A[i] < x i=i+1 while x < A[j] j=j-1 if i <= j then begin Swap(A[i], A[j]) i=i+1 j=j-1 endif enddo while i <= j
if low < j then qSort(A, low, j) if i < high then qSort(A, i, high) return A endfunction
Эмпирический анализ и исследование производительности для каждого алгоритма в отдельности. Оценка количества сравнений, обменов и времени работы алгоритма. Входные данные – массив размерности n – оцениваются размером массива и степенью отсортированности: не отсортированный, полностью отсортированный и отсортированный в обратном порядке. · сортировка выбором Алгоритм сортировки выбором относится к не рекурсивным алгоритмам. Основная операция – сравнение. Количество основных операций зависит от данных.
Количество основных операций: То есть алгоритм сортировки выбором относится к квадратичному классу эффективности, поэтому он не эффективный для сортировки массивов больших чисел. Количество сравнений для всех случаев одинаковое. Для случая отсортированного массива количество обменов равно нулю.
· простая сортировка вставкой Алгоритм простой сортировки вставками относится к не рекурсивным алгоритмам. Основная операция – сравнение. Количество основных операций зависит от данных. Количество основных операций в худшем случае: То есть алгоритм простой сортировки вставками относится к квадратичному классу эффективности, поэтому он не эффективный для сортировки массивов больших чисел.
· сортировка слиянием Алгоритм сортировки слиянием относится к рекурсивным алгоритмам. Основная операция – сравнение. ВОПРОС: спавнение счит-ся только элементов массива, или любые сравнения в алгоритме? Количество основных операций зависит от данных. Рекуррентное уравнение, выражающее количество выполняемых операций сравнения: То есть алгоритм сортировки слиянием относится к классу эффективности
· быстрая сортировка Алгоритм быстрой сортировки относится к рекурсивным алгоритмам. Основная операция – сравнение. Количество основных операций зависит от данных. Рекуррентное уравнение, выражающее количество выполняемых операций сравнения: То есть алгоритм быстрой сортировки относится к классу эффективности
4.Сравнение производительностей алгоритмов для массивов из Для каждого примера рассмотрим случаи: а) случайно сгенерированные числа в диапазоне [1..n] б) последовательность чисел 1, 2, …, n в) последовательность чисел n, n-1, …,1 · сортировка выбором Количество сравнений для всех случаев одинаковое, так как для поиска минимального элемента массива алгоритм в любом случае сравнивает все элементы. Для случая отсортированного массива количество обменов равно нулю, поскольку первый элемент уже будет минимальным, и обмен выполняться не будет.
· простая сортировка вставкой Для случая уже отсортированного массива алгоритм не будет выполнять обмен, поскольку большее число будет всегда стоять справа от меньшего. Для случая массива отсортированного в обратном порядке количество сравнений и обменов наибольшее, так как сравнивать и менять местами необходимо абсолютно каждое число. · сортировка слиянием Видим, что для данной сортировки количество обменов всегда равно нулю, так как в алгоритме не выполняется обменов местами элементов массива. А создается буферный массив размера заданного, и, после сравнения элементов 2-х подпоследовательностей, в буферный массив добавляем сначала меньшее число а затем большее. · быстрая сортировка Приупорядоченном массиве обменов будет меньше всего, так как элементы меньше среднего числа уже будут стоять слева от него, а больше – справа. Для массива, отсортированного в обратном порядке, сравнений будет меньше всего, так как при первом же сравнении сразу будут находиться числа, которые нужно поменять местами. · сортировка выбором · простая сортировка вставкой По графическим представлениям мы видим, что алгоритмы сортировки выбором и простой сортировки вставкой действительно принадлежат к классам эффективности квадратичной сложности. · сортировка слиянием · быстрая сортировка По графическим представлениям мы видим, что алгоритмы сортировки слиянием и быстрой сортировки действительно принадлежат к классам эффективности
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|