Adaptivity

Lesson 6 of 11 in Coddy's Bubble Sort course.

We have discussed the time complexity for our bubble sort algorithm, which is O(n²) . But, what if our array is already sorted? then also, it will take the runtime of O(n²).

What is Adaptivity?

An adaptive algorithm is an algorithm that changes its behavior on given input sequence.

So, is bubble sort adaptive?

Yes, we can make our bubble sort algorithm adaptive. We have to write the Bubble Sort algorithm with worst case runtime of O(n²) and best case of O(n) so that it is adaptive. Here, best case refers to the case when array is already sorted.

We will use a boolean flag variable to control the while loop so that the algorithm would stop early if it was sorted before.

while(flag)

{

//code

}

We have to repeat the pass until the array is sorted. We have already learned how to count number of swaps, so we can implement a flag and check if there is no swap required in the pass and then we can break the loop.

Challenge

Medium

Create a function named ad_bubblesort that receives an array and size of the array. Perform adaptive bubble sort algorithm. Remember to use a variable named flag to check for swaps.

Try it yourself

#include <stdio.h>
#include <stdlib.h>

int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
    // Write code here
    *returnSize = n;
    return arr;
}

All lessons in Bubble Sort

1Basics of Bubble Sort

Introduction Working of the Bubble Sort Swap adjacent elements Bubble Sort Algorithm

2Analysis

Complexity AnalysisAdaptivityStability

3Practice Challenges

Reverse Sort Min-Max Difference kth smallest element Abhinav and his friends