Algorithm Analysis and Design Consider Bubble sort a Prove t

Algorithm Analysis and Design

Consider Bubble sort:
a. Prove that if bubble sort makes no exchanges on its pass through a list, the list is then sorted and the algorithm can be stopped.
b. Write pseudocode of the method that incorporates this improvement.
c. Prove that the worst-case efficiency of the improved version is still quadratic.

Solution

a) Pass i (0 i n2) of bubble sort can be represented by the following diagram:

A0, ..., Aj Aj+1, ..., Ani1 | Ani ... An1 in their final positions

If there are no swaps during this pass, then

A0 A1 ... Aj Aj+1 ... Ani1,

with the larger elements in positions n – I through n 1 being sorted during the previous iterations.

b)

Algorithm BetterBubbleSort(A[0..n 1])

count <- n 1

sflag <- true

while sflag do

sflag <- false

for j <- 0 to count1 do

if A[j + 1] < A[j]

swap A[j] and A[j + 1]

sflag <- true

count <- count 1

c)

The worst-case inputs will be strictly decreasing arrays. For them, the improved version will make the same

comparisons as the original version, which was shown in the text to be quadratic.