We learnt bubble sort in class, which could be implemented so easily:
void bubble_sort(int *begin, int *end)
{
for (; begin < end; end--)
for (int *ptr = begin + 1; ptr < end; ptr++)
if (*(ptr - 1) > *ptr)
iter_swap(ptr - 1, ptr);
}Short as the codes might be, it doesn't run efficiently at all. It's obvious that he number of comparisons (the if branch) would be executed \(\sum^{i=n-1}_1i\) times. In fact, we could improve the performance slightly since if inside the second for loop there's no any swap required, then the sorting is already done and no longer need to compare or swap any more.
On the other hand, the number of swaps, which equals the number of inversions, is the bottleneck of bubble sort, constraining the time complexity.
So given an array, you are to compute the two number mentioned above: minimum number of comparisons and number of swaps that bubble sort take.
The first line is an integer \(n<10^4\) indicating the length of the array.
The next line contains the \(n\) integers \(a_i\in[-2^{31},2^{31})\) of the array.
Please print two integers, the number of comparisons and number of swaps, separated by a space. Remember to put a '\n' at the end of line.