I understand that the big O values for Bubble Sort and Selection Sort are the same, (n)^2, but when I try to run both with an array of size 1000, the Bubble Sort takes 962037 swaps to sort the array, while Selection Sort only takes 988 swaps to sort the array. Why are these different?
可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):
问题:
回答1:
Because the complexity refers to the number of comparisons, not the number of swaps. Both need O(n^2) comparisons, but selection sort needs only n-1 swaps in the worstcase (O(n)), whereas bubblesort might need up to n*(n-1)/2 swaps (O (n^2)).
And even if the complexity would refer to the number of swaps - as the notation ignores constants (one could actually be 1000*n^2 + 500*n*log(n) + 100*n + 10, while the other could be n^2), both numbers could still differ by an abritrary large value.
回答2:
The Big O notation provides the asymptomatic cost, however, all additive values and constants are omitted. In addition, for a realistic comparison for small numbers, you need to look at the average number of comparisons. More specifically, Bubble sort requires, on average, n/4 swaps per entry , while Selection sort requires only 1, see this post for further details. The number of comparisons will also depend on the initial distribution, for example whether the data is semi-sorted or completely random.
