Bubble Sort(Advanced/ Modified)

[ Home Page ]  [ Back ]  [ Content of Contributions ]  [ Movement: Green Leaf World ]

Algorithm: Advanced_Bubble_Sort ( A, N )

Here, A is any numerical array with N number of unordered values. This algorithm will arranged the values in non-decreasing order.

Assuming, index of the array is started from 0.

Steps:

1/ Scan:= 1

2/ WHILE Scan < N, Do

     Flag:= 0

     i:= 0

     WHILE i < (N-Scan), Do

       IF A(i) > A(i+1), then

         Interchange A(i) and A(i+1)

         Flag:= 1 

       End of IF

       IF Flag=1, then      

         i:= (i+1)
       ELSE
         RETURN
       End of IF

     End of WHILE (Inner Loop)

     Scan:= (Scan+1)

   End of WHILE (Outer Loop)

3/ RETURN

In this algorithm, consecutive values are comparing for their existing order, if it is not the desire order then interchanging consecutive values to maintain ordering between every consecutive values. When, all the consecutive values will be in same order, the entire set will be in the same order. As per the algorithm, in every iteration(Scan), the largest value among index 0 to index (N-Scan) will be placed in the index (N-Scan). After iteration(Scan) number i, values at index (N-i) to (N-1) will be arranged in the desired order.

This algorithm works similar to that Bubble Sort method but the only difference is that, in this algorithm, if the data set is arranged in any intermediate iteration(Scan), the computation will stop after next iteration(Scan). So, for a data set which is initially arranged in the same order as desire, then, computation will stop after Scan 1, total comparisons required (N-1). Also for a data set which is initially arranged in the reverse order as desire, then, computation will stop after Scan= (N-1), total comparisons required 

(N-1) + (N-2) + . . . . + 2 + 1. 

 

Try Your Own

Consider the set {9, 1, 8, 2, 7, 3, 6, 4}. Test Bubble Sort and Advance Bubble Sort algorithm on this data set and calculate Scan wise comparisons & total number of comparisons required by Bubble Sort and Advanced Bubble Sort.

Consider the set {1, 2, 3, 4, 5, 6}. Test Bubble Sort and Advance Bubble Sort algorithm on this data set and calculate Scan wise comparisons & total number of comparisons required by Bubble Sort and Advanced Bubble Sort.

Consider the set {6, 5, 4, 3, 2, 1}. Test Bubble Sort and Advance Bubble Sort algorithm on this data set and calculate Scan wise comparisons & total number of comparisons required by Bubble Sort and Advanced Bubble Sort.