8.3.3 Timing the Bubble Sort

If the array were initially given in sorted order, only one pass would be required, and the time would be proportional to n. If the array were initially given in reverse sorted order, then n - 1 passes would be required, with (n - 1 - k) interchanges and comparisons. This is the worst case, and takes time determined by the (n - k) interchanges and comparisons. This sum is (n - 1) + (n - 2) + ?/FONT> ?/FONT> ?/FONT> + 1 or [n(n - 1)]/2 interchanges and comparisons. The worst-case time for the bubble sort is O(n²), just as for the maximum entry sort. However, the maximum entry sort will always take time O(n²), since the number of comparisons it makes is not dependent on the data. The time taken by the bubble sort thus varies from O(n) for sorted data to O(n²) for reverse sorted data. The more ordered the initial data, the shorter the time.