Consider the two algorithms below: BubbleSort( A[1, . . . , n], array of integer
ID: 650058 • Letter: C
Question
Consider the two algorithms below:
BubbleSort( A[1, . . . , n], array of integers)
1. For i ? 1 To n-1
2. For j ? 1 To n-i
3. If A[j] > A[j+1] Then
4. Interchange A[j] and A[j+1]
RevisedBubbleSort( A[1, . . . , n], array of integers)
1. For i ? 1 To n-1
2. done ? true
3. For j ? 1 To n-i
4. If A[j] > A[j+1] Then
5. Interchange A[j] and A[j+1]
6. done ? false
7. If done Then Break
What is the difference between these two algorithms? How many comparisons does RevisedBubbleSort make if array is sorted from smallest to largest? How many comparisons does RevisedBubbleSort make if array is sorted from largest to smallest?
Explanation / Answer
Difference between two algorithms:
Bubble Sort:
In this algorithm :
n*(n+1)/2 number of times loop will run where n is the number of elements which will compare the adjacent numbers if the number before is greater than the after one then it will be swapped.
RevisedBubbleSort:
In this algorithm:
Number of times looping will be done depends on how much array is sorted thus its complexity is always lesser or equal to the above algorithm.
Which is n <= Complexity <= (n*(n+1))/2
How many comparisons does RevisedBubbleSort make if array is sorted from smallest to largest?
if the array is sorted then the number of comparison will be equal to the number of elements. as the inner loop will run through all the elements to check if there is any sorting mismatch is there or not.
How many comparisons does RevisedBubbleSort make if array is sorted from largest to smallest?
If the array is reverse sorted the number of comparisons happening will be maximum that is (n*(n+1))/2. Because in each iteration of i with j largest element will be positioned to last.