Bubble Sort Algorithm-Multiple Choice Question

Question

A Bubble Sort algorithm as discussed in lectures is given below

index1 = 1;

repeat exchange = false;

{ for index2 ← length – 1 downto index1

{ if data[index2] < data[index2-1]

{ //exchange

exchange = true;

tmp = data[index2];

data[index2] = data[index2-1];

data[index2-1] = tmp;

}

}

index1 = index1 + 1;

} until (not exchange)

Apply this algorithm to the following data. Give the contents of the array after each pass (repeat loop) is completed. For each pass how many exchanges are made?

Note it may not be necessary to use all 7 passes.

                    Original Data 14 27 12 56 63 72 8 10

After             Pass 1

                 Exchanges

After             Pass 2

                 Exchanges

After            Pass 3

                 Exchanges

After           Pass 4

               Exchanges

After        Pass 5

              Exchanges

After         Pass 6

              Exchanges

After         Pass 7

             Exchanges

How many comparisons will be made in total?