Question

1. For each of the following lists, perform a bubble sort, and show the list after each exchange:

D,B,G,F,A,C,E,H

2. Explain why the bubble sort algorithm does O (n^2) comparisons on an n-element list.

Answer 1

Thanks for the question. Here are the answers with explanations.

=========================================================================================

Question 1

Here are the list after each exchange

D B G F A C E H   
B D G F A C E H   
A D G F B C E H    
A B F G D C E H
A B D G F C E H
A B C G F D E H
A B C F G D E H
A B C D G F E H
A B C D F G E H
A B C D E G F H
A B C D E F G H

Question 2

In bubble sort we are having two loops, the second loop is nested inside another for loop, the outer loop runs for each element in the list so if there are n elements we are iterating over n times

the inner loop runs 1 less than the current loop

so for the 1st pass the inner loop runs n-1 times

for the 2nd pass the inner loop runs for n-2 times

for the n-1th pass the inner loop runs for 1 time

for the nth pass the inner loops runs for 0 times

hence if we add all the inner loop runs we get the series like = 1+2+3+... +(n-2)+(n-1) which is n*(n-1)/2

which when simplified we get of order n^2