Complexity Analysis
Урок 5 из 11 курса Пузырьковая сортировка на Coddy.
Анализ сложности пузырьковой сортировки.
Временная сложность зависит от количества выполненных сравнений и перестановок.
Нам нужно выполнить n проходов, и в каждом проходе у нас есть (n-1) сравнений. Где n — это количество элементов в списке.
Всего сравнений=(n-1)+(n-1)+(n-1)....n раз
=n*(n-1)
=n2-n
Временная сложность алгоритма пузырьковой сортировки составляет O(n2).
Если говорить о пространственной сложности, в алгоритме не используется дополнительное пространство, выполняется сортировка на месте (in-place), и элементы упорядочиваются в самом исходном списке.
Пространственная сложность алгоритма пузырьковой сортировки составляет O(1) (Константа).
Задание
ЛегкоСоздайте функцию с именем count_swaps, которая принимает массив и размер массива. Выполните алгоритм пузырьковой сортировки (bubble sort) для этого массива и подсчитайте количество выполненных перестановок.
Попробуйте сами
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Напишите код здесь
return 0;
}
Все уроки раздела Пузырьковая сортировка
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm