Adaptivity
Урок 6 из 11 курса Пузырьковая сортировка на Coddy.
Мы обсудили временную сложность нашего алгоритма пузырьковой сортировки, которая составляет O(n2) . Но что, если наш массив уже отсортирован? Тогда он все равно потребует времени выполнения O(n2).
Что такое адаптивность?
Адаптивный алгоритм — это алгоритм, который меняет свое поведение в зависимости от заданной входной последовательности.
Итак, является ли пузырьковая сортировка адаптивной?
Да, мы можем сделать наш алгоритм пузырьковой сортировки адаптивным. Нам нужно написать алгоритм пузырьковой сортировки с временем выполнения в худшем случае O(n2) и в лучшем случае O(n), чтобы он был адаптивным. Здесь лучший случай относится к ситуации, когда массив уже отсортирован.
Мы будем использовать логическую переменную-флаг (boolean flag) для управления циклом while, чтобы алгоритм мог завершиться раньше, если массив был отсортирован досрочно.
while(flag)
{
//code
}
Нам нужно повторять проход до тех пор, пока массив не будет отсортирован. Мы уже научились считать количество перестановок, поэтому мы можем реализовать флаг и проверять, не требуются ли перестановки во время прохода, и тогда мы сможем прервать цикл.
Задание
СреднеСоздайте функцию с именем ad_bubblesort, которая принимает массив и размер массива. Реализуйте алгоритм адаптивной пузырьковой сортировки. Не забудьте использовать переменную с именем flag для проверки наличия перестановок.
Попробуйте сами
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// Напишите код здесь
*returnSize = n;
return arr;
}
Все уроки раздела Пузырьковая сортировка
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm