Explain Bubble sort algorithm and simulate it for the following data 35, 33, 42, 10, 14, 19, 27, 44. Also find the number of comparisons and interchanges.

Q.) Explain Bubble sort algorithm and simulate it for the following data 35, 33, 42, 10, 14, 19, 27, 44. Also find the number of comparisons and interchanges.

 Subject: data structures

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

The algorithm gets its name from the way smaller or larger elements "bubble" to the top of the list.

Here's a step-by-step breakdown of how Bubble Sort would sort the list 35, 33, 42, 10, 14, 19, 27, 44:

  1. First Pass:

    • (35, 33, 42, 10, 14, 19, 27, 44) -> (33, 35, 42, 10, 14, 19, 27, 44), Here, algorithm compares the first two elements, and swaps them.
    • (33, 35, 42, 10, 14, 19, 27, 44) -> (33, 35, 42, 10, 14, 19, 27, 44), Swap since 35 < 42
    • (33, 35, 42, 10, 14, 19, 27, 44) -> (33, 35, 10, 42, 14, 19, 27, 44), Swap since 42 > 10
    • (33, 35, 10, 42, 14, 19, 27, 44) -> (33, 35, 10, 14, 42, 19, 27, 44), Swap since 42 > 14
    • (33, 35, 10, 14, 42, 19, 27, 44) -> (33, 35, 10, 14, 19, 42, 27, 44), Swap since 42 > 19
    • (33, 35, 10, 14, 19, 42, 27, 44) -> (33, 35, 10, 14, 19, 27, 42, 44), Swap since 42 > 27
    • (33, 35, 10, 14, 19, 27, 42, 44) -> (33, 35, 10, 14, 19, 27, 42, 44), Now, since these elements are already in order (42 < 44), algorithm does not swap them.

  2. Second Pass:

    • (33, 35, 10, 14, 19, 27, 42, 44) -> (33, 35, 10, 14, 19, 27, 42, 44)
    • (33, 35, 10, 14, 19, 27, 42, 44) -> (33, 10, 35, 14, 19, 27, 42, 44)
    • (33, 10, 35, 14, 19, 27, 42, 44) -> (33, 10, 14, 35, 19, 27, 42, 44)
    • (33, 10, 14, 35, 19, 27, 42, 44) -> (33, 10, 14, 19, 35, 27, 42, 44)
    • (33, 10, 14, 19, 35, 27, 42, 44) -> (33, 10, 14, 19, 27, 35, 42, 44)
    • (33, 10, 14, 19, 27, 35, 42, 44) -> (33, 10, 14, 19, 27, 35, 42, 44)

  3. The process goes on until the entire list is sorted.

In Bubble Sort, n-1 comparisons will be done in the 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be,

(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1 Sum = n(n-1)/2 i.e O(n^2)

Hence the time complexity of Bubble Sort is O(n^2).

In the above example, number of comparisons = 8(8-1)/2 = 28 and number of interchanges = 6 (actual number of swaps may vary depending on the initial arrangement of the list).