The number of comparisons required for bubble sorting of an array of n elements is
The number of comparisons required for bubble sorting of an array of n elements is ________
a) n(n-1)/2
b) n/2
c) log2n
d) log10n
The number of comparisons required for bubble sorting of an array of n elements is ________
a) n(n-1)/2
b) n/2
c) log2n
d) log10n
Best answer
A) n(n-1)/2
Is the right answer
Answer: (a) \(\dfrac{n(n-1)}{2}\)
Bubble sort compares adjacent pairs. In the first pass it makes \(n-1\) comparisons, in the second \(n-2\), and so on until 1 comparison in the last pass:
\[(n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}.\]
That is why bubble sort is \(O(n^{2})\). (An optimised version stops early if a pass makes no swaps, but the standard count asked in exams is \(n(n-1)/2\).)
Log in or create a free account to answer this question.