|
I have a quick question on the bubble sort algorithm. Why does it perform $\Theta(n^2)$ comparisons on an $n$ element list? I looked at the Wikipedia page and it does not seem to tell me. I know that because of its magnitude it takes a lot of work with large numbers. |
||||
|
|
|
Consider the worst case analysis: when the array is completely sorted, but from largest to smallest. In this case, bubble sort will make $n-i$ swaps in iteration $i$ (and in particular, there will be a swap in every iteration), and repeat that for $n-1$ times. This gives a total runtime of $(n-1)^2=\theta(n^2)$. Observe that even under some optimizations of the naive bubble sort, the runtime is still ${n\choose 2}=\theta(n^2)$. |
|||
|
|
|
I have to disagree slightly with what Shaull said, although it still comes out to the same big-theta run time. It is true that the first element in a reversely sorted list will have n-1 comparisons, but each suqsequent element will have one less. Leading to $\sum_{i=o}^{n-1} i = \frac{n(n-1)}{2}$ number of comparisons, which still comes out to $\Theta(n^2)$ number of comparisons. |
||||
|
