1.0042 Given a list of 1,453 (unsorted) elements to be sorted using a bubble-sort, what is the maximum number of passes needed? The maximum number of comparisons?
The maximum number of passes required is defined as n – 1, where n is the number of elements. In this case, the maximum number of passes necessary is n – 1 = 1,453 – 1 = 1,452.
The maximum number of comparisons needed is defined as (n2 – n)/2 = (1,4532 – 1,453)/2 = (2,111,209 – 1,453)/2 = 2,109,756/2 = 1,054,878