Question

Explain Bubble Sort Algorithm with. suitable example.

Answer 1

Algorithm:
[Bubble Sort] BUBBLE [DATA, N]
Here DATA is an array with N elements. This algorithm sorts the  elements in DATA.
(1) Repeat steps 2 and 3 for K = 1 to N-1
(2) Set PTR: = 1 [ pass pointer PTR.]
(3) Repeat while PTR<= N–K. [Executes pass.]
     (a) IF DATA [PTR] > DATA [PTR + 1], then:
          Interchange DATA [PTR] and DATA [PTR + 1]
          [End of IF structure]
     (b) Set PTR: = PTR + 1
          [End of inner loop.]
          [End of step 1 outer loop.]
(4) Exit.
    Example:
    Consider the array as follows:

DATA[1]	56
DATA[2]	43
DATA[3]	05
DATA[4]	07
DATA[5]	09

Pass 1:
(a) Compare DATA [1] with DATA [2] since 56>43 So it is  exchanged,
                        56    43    5    7    9
New list is →    43    56    5    7    9

(b) Compare DATA [2] with DATA [3] since 56 >5 so it is exchanged,
                       43    56    5     7     9
New list is →   43    5     56    7     9

(c) Compare DATA [3] with DATA [4] since 56>7 so it is exchanged,
                        43    5    56    7    9
New list is →    43    5    7     56   9
(d) Compare DATA [4] with DATA [5] since 56>9 so it is exchanged,
                       43    5    7    56    9
New list is →   43    5    7    9    56
At the end of first pass, the largest element 56 has moved to the last position.

Pass 2 : As K=2 , the comparisons will be 3.
New list is     43    5    7    9    56

(a) 43   5    7    9    56 since 43>5 exchange
     5     43   7   9    56

(b) 5    43  7    9   56 since 43>7 exchange
     5    7   43   9   56

(c) 5    7   43  9   56 since 43>9 exchange
     5    7   9    43 56

Pass 3:
5   7   9   43   56 No exchange
5   7   9   43   56 No exchange
New List:
5   7   9   43   56

Pass 4:
In this way after complete execution of this algorithm, the array gets sorted in Ascending order as follows:

DATA[1]	5
DATA[2]	7
DATA[3]	9
DATA[4]	43
DATA[5]	56