Given an array, arr[]. Sort the array using bubble sort algorithm. Input…

Concept. Bubble sort is a comparison-based, in-place sorting method resting on one invariant: a single left-to-right scan that swaps every adjacent pair found out of order drives the largest value of the scanned region to that region’s right-hand end. Repeating the scan therefore locks one more of the largest values into its final position each time, so after at most n − 1 scans every element sits where it belongs.

Standard form of the algorithm

for i from 0 to n-2:
    swapped = false
    for j from 0 to n-2-i:
        if arr[j] > arr[j+1]:
            swap(arr[j], arr[j+1])
            swapped = true
    if not swapped:
        break        // no adjacent pair is out of order => already sorted

Application. Trace arr[] = [4, 1, 3, 9, 7], n = 5.

Pass 1 (compare each adjacent pair from the left):

1. 4 and 1 are out of order → swap → [1, 4, 3, 9, 7]

2. 4 and 3 are out of order → swap → [1, 3, 4, 9, 7]

3. 4 and 9 are already in order → no swap

4. 9 and 7 are out of order → swap → [1, 3, 4, 7, 9]

The largest value, 9, has now been carried to the last index, so index 4 is finalised and pass 2 only needs to scan the first four elements.

Pass 2:

1. 1 and 3 are in order → no swap

2. 3 and 4 are in order → no swap

3. 4 and 7 are in order → no swap

The whole pass produced zero swaps. “No adjacent pair is out of order” is precisely the definition of a sorted array, so the swapped flag is false and the algorithm stops early. Final array: [1, 3, 4, 7, 9].

Cross-check against the other two samples

• [1, 2, 3, 4, 5] is already sorted, so pass 1 performs its 4 comparisons, makes 0 swaps, and the early exit returns the array unchanged — the best case, Θ(n).

• [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] is fully reversed, so every comparison triggers a swap: all 9 passes run and 9 + 8 + … + 1 = 45 swaps are made before the output [1, 2, …, 10] appears — the worst case, Θ(n2).

Cost and correctness properties

• Comparisons in the worst case total n(n − 1)/2. With the stated bound n ≤ 103 that is at most 499500 comparisons, so the plain quadratic algorithm fits comfortably inside a 2 s limit — no faster sort is needed here.

• Auxiliary space is O(1): only one temporary is used for the swap, and the array is rearranged in place.

• Bubble sort is stable, because a pair is swapped only on a strict arr[j] > arr[j+1]; two equal values are never exchanged and so keep their original relative order.

• Skipping the last i positions in pass i + 1 is safe exactly because the invariant guarantees those positions already hold the i largest values in final order.

Result. Repeated adjacent-swap passes, with an early exit as soon as a pass makes no swap, sort the array ascending in place: [4, 1, 3, 9, 7] → [1, 3, 4, 7, 9].