Answer to Q3:
The task is to sort the array A = [1, 2, 3, 4, 9, 8, 7, 6, 5] using the Bubble Sort
algorithm.
Size of the array n is 9.
Bubble sort works by repeatedly stepping through the list, comparing each pair of
adjacent items and swapping them if they are in wrong order. Each pass through list
places the next largest value in its proper place.
1.1. Time complexity
Time complexity of Bubble Sort algorithm in worst-case and average-case
is O(n²) (Quadratic Time Complexity). This is because for array of size n, it
performs about n passes, and each pass has up to n-1 comparisons, making
a nested-loop structure.
1.2. Total number of pass
Standard Bubble Sort algorithm always performs n-1 passes to ensure array is sorted.
For this array, n = 9.
Total number of passes = 9 - 1 = 8 passes.
(Note: Optimized version of Bubble Sort might end earlier if a pass completes
with no swaps. For this array, it sorts after 4 passes and stops after 5th pass confirms
sorted. But
the standard algorithm does all 8 passes.)
1.3. Total number of comparisons
In standard Bubble Sort algorithm, total number of comparisons is sum of
comparisons in each pass: (n-1) + (n-2) + + 1. This can be found with formula:
Total comparisons = n * (n - 1) / 2
Total comparisons = 9 * (9 - 1) / 2 = 9 * 8 / 2 = 36 comparisons.
1.4. Array after 3 pass?
We will see array state after first three passes. In each pass, largest unsorted element
"bubbles up" to its position.
Initial Array: [1, 2, 3, 4, 9, 8, 7, 6, 5]
Pass 1: Goal is to move largest element (9) to last position. Comparisons and swaps
are like this:
(4, 9) -> no swap
(9, 8) -> swap: [..., 4, 8, 9, 7, ...]
(9, 7) -> swap: [..., 8, 7, 9, 6, ...]
(9, 6) -> swap: [..., 7, 6, 9, 5]
(9, 5) -> swap: [..., 6, 5, 9]
After this pass, largest element, 9, is at the end.
Array after 1 pass: [1, 2, 3, 4, 8, 7, 6, 5, 9]
Pass 2: Goal is to move next largest element (8) to second to last position. We only
iterate through first n-1 = 8 elements.
(4, 8) -> no swap
(8, 7) -> swap: [..., 4, 7, 8, 6, ...]
(8, 6) -> swap: [..., 7, 6, 8, 5, ...]
(8, 5) -> swap: [..., 6, 5, 8, ...]
After this pass, 8 is in its position.
Array after 2 passes: [1, 2, 3, 4, 7, 6, 5, 8, 9]
Pass 3: Goal is to move next largest element (7) to its position. We only
iterate through first n-2 = 7 elements.
(4, 7) -> no swap
(7, 6) -> swap: [..., 4, 6, 7, 5, ...]
(7, 5) -> swap: [..., 6, 5, 7, ...]
After this pass, 7 is in its position.
Array state after 3 passes is: [1, 2, 3, 4, 6, 5, 7, 8, 9]