Bubble sort is a simple sorting algorithm. It compares each adjacent pair and check if the

elements are in order. If they aren$$t$,$ the elements are swapped. This process continues until all

elements are sorted.

If there is an integer array of n elements, and the algorithm output the array in an increasing

order $($from smallest to the largest$),$ the bubble sort can be implemented as

for$($int i $=0$;i $<$ n; i$++)\{$

for$($int j$=0$;j $<$ n $-1$; j$++)\{$

if$($arr$[$j$]>$ arr$[$j$+1])\{$

int temp $=$ arr$[$j$]$;

arr$[$j$]=$ arr$[$j$+1]$;

arr$[$j$+1]=$ temp;

$\}$

$\}$

$\}$

You have an array X$=[1,2,3,...,$n$]$ and an array Y$=[$n$,$n$-1,$n$-2,...,1].$ So$,$ X represents the best case

$($the array is already sorted$)$ and Y represents the worst case $($the array is sorted reversely$).$

$1)$ Analyze the above bubble sort and calculate the total number of operations with input X and

Y$,$ respectively.

There is another way of implementing bubble sort where the algorithm also checks if the array

has been sorted $($to improve the efficiency$).$ We create a flag that checks if a swap has occurred

between any adjacent pairs. If there is no swap while traversing the entire array, the array is

completely sorted, and the algorithm can break out of the loop. This is called a revised bubble

sort. It can be implemented as

$-5-$

for$($int i $=0$;i $<$ n; i$++)\{$

boolean isSwapped $=$ false;

for$($int j$=0$;j $<$ n $-1$; j$++)\{$

if$($arr$[$j$]>$ arr$[$j$+1])\{$

int temp $=$ arr$[$j$]$;

arr$[$j$]=$ arr$[$j$+1]$;

arr$[$j$+1]=$ temp;

isSwapped $=$ true;

$\}$

$\}$

if$(!$isSwapped$)\{$

break;

$\}$

$\}$

$2)$ Analyze the above revised bubble sort and calculate the total number of operations with

input X and Y$,$ respectively.

Note: you MUST include the calculation steps and explain how you get the answers