QUESTION 23 · Sorting

What does one left-to-right bubble-sort pass achieve?

2 marks

Answer

It moves the largest value in the current unsorted part to its final rightmost position.

Adjacent out-of-order values are swapped.
This optimised version stops when a complete pass makes no swaps.

Explain bubble sort and write a C program to sort integers in ascending order.

5 marks

Answer in brief

Bubble sort repeatedly compares adjacent values and swaps them when they are in the wrong order.

Algorithm

For each pass, scan adjacent pairs in the unsorted part.
Swap a[j] and a[j + 1] when the left value is larger.
Exclude the newly fixed rightmost value from the next pass.
Stop early if a full pass makes no swaps.

Worked trace

For 5, 1 and 4, compare 5 with 1 and swap, giving 1, 5, 4. Compare 5 with 4 and swap, giving 1, 4, 5. The largest value 5 is now fixed. The next pass compares 1 with 4 and makes no swap, so the algorithm stops.

Why it works

Each adjacent comparison moves the larger of the pair one position right. Across a pass, the largest remaining value keeps moving until it reaches the final unsorted position. Repeating this step fixes one more position each time.

Time complexity

In reverse order, the comparisons can total (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2, giving O(n²) time. With the swapped flag, already sorted input needs only one pass of n - 1 comparisons, giving O(n) best-case time. Average performance is also quadratic under usual input models.

Space and stability

Only a few counters, a flag and a temporary value are added, so auxiliary space is O(1). This version swaps only when the left value is strictly larger. Equal values do not cross through a swap, so it is stable. The input array itself is rearranged.

Diagram or flowchart

CodeBhavya illustration of bubble sort. — Explain bubble sort and write a C program to sort integers in ascending order. · Download diagram

C program and output

Download .c Open compiler

/* CodeBhavya | PPS AR25 | Learning example */
#include <stdio.h>
void sort(int a[], int n)
{
    for (int pass = 0; pass < n - 1; ++pass) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - pass; ++j) {
            if (a[j] > a[j + 1]) {
                int temporary = a[j]; a[j] = a[j + 1]; a[j + 1] = temporary;
                swapped = 1;
            }
        }
        if (!swapped) { break; }
    }
}

int main(void)
{
    int n, a[20];
    if (scanf("%d", &n) != 1 || n < 1 || n > 20) {
        puts("Unsupported input"); return 1;
    }
    for (int i = 0; i < n; ++i) {
        if (scanf("%d", &a[i]) != 1 || a[i] < -10000 || a[i] > 10000) {
            puts("Unsupported input"); return 1;
        }
    }
    sort(a, n);
    for (int i = 0; i < n; ++i) {
        if (i > 0) { putchar(' '); }
        printf("%d", a[i]);
    }
    putchar('\n');
    return 0;
}

Sample input and output

Input

3
5 1 4

Output

1 4 5