For a list of length n, the bubble sort makes exactly ____ key comparisons.
A) n(n-1)/2
B) n(n-1)/3
C) n(n-1)/4
D) (n-1)/2

Name: For a list of length n, the bubble sort makes exactly ____ key comparisons. A) n(n-1)/2 B) n(n-1)/3 C) n(n-1)/4 D) (n-1)/2
Brand: Quizplus
Rating: 4.9 (28 reviews)

Question

Quizplus · Accepted Answer

The bubble sort algorithm makes n-1 passes through the list and makes n-i-1 comparisons on the ith pass. Therefore, the total number of comparisons is:
(n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2. Option A matches this formula.

For a List of Length N, the Bubble Sort Makes