Question

Bubble sort is a sorting algorithm that works as follows: Go through the input list/array element by element, comparing the current element with the one that follows it (i.e. compare A[i] with A[i+1]), then swap the two values if they are not sorted. These process is repeated through the list until no swaps can be performed during a pass, meaning that the list is already sorted. Given the following elements:
23 32 72 76 22 73 40 30 20 60 16 74 28 14
i) Show the needed steps for sorting these values into ascending order using Bubble Sort.
ii) Does Bubble Sort have better time complexity compared to Selection Sort? Explain.

Answer 1

Explanation:

i) Steps for sorting the given elements into ascending order using Bubble Sort:

1. Start with the given list of elements:

23 32 72 76 22 73 40 30 20 60 16 74 28 14

2. Compare each element with the one that follows it, and swap if necessary:

23 32 72 22 73 40 30 20 60 16 74 28 14 76 (swapped 76 and 22)

23 32 22 72 40 30 20 60 16 73 28 14 74 76 (swapped 72 and 22)

23 22 32 40 30 20 60 16 72 28 14 73 74 76 (swapped 32 and 22)

Repeat the process until no more swaps are needed.

3. Continue the process:

22 23 32 30 20 40 16 60 28 14 72 73 74 76 (swapped 40 and 30)

22 23 30 20 32 16 40 28 14 60 72 73 74 76 (swapped 32 and 30)

22 23 20 30 16 32 28 14 40 60 72 73 74 76 (swapped 20 and 16)

22 20 23 16 30 28 14 32 40 60 72 73 74 76 (swapped 23 and 20)

Repeat until no more swaps are needed.

4. Continue:

20 22 16 23 28 14 30 32 40 60 72 73 74 76 (swapped 22 and 16)

20 16 22 23 14 28 30 32 40 60 72 73 74 76 (swapped 23 and 16)

16 20 22 14 23 28 30 32 40 60 72 73 74 76 (swapped 20 and 16)

Repeat until no more swaps are needed.

5. Continue:

16 20 14 22 23 28 30 32 40 60 72 73 74 76 (swapped 22 and 14)

16 14 20 22 23 28 30 32 40 60 72 73 74 76 (swapped 20 and 14)

Repeat until no more swaps are needed.

6. Continue:

14 16 20 22 23 28 30 32 40 60 72 73 74 76 (swapped 16 and 14)

Repeat until no more swaps are needed.

The sorted list is: 14 16 20 22 23 28 30 32 40 60 72 73 74 76

ii) Bubble Sort and Selection Sort both have average and worst-case time complexities of O(n^2). However, Bubble Sort typically requires more swaps than Selection Sort, especially in the worst-case scenario. Selection Sort tends to be more efficient in practice due to its lesser number of swaps. Therefore, while both algorithms have the same time complexity, Selection Sort often performs better than Bubble Sort in real-world scenarios.