Medium · sorting

Bubble Sort

The first algorithm that changes data instead of just inspecting it. You already know how to compare two numbers — sorting is comparing every pair, in the right order.

At a glanceSwap adjacent out-of-order pairs until a whole pass makes no swaps — O(n²), and n ≤ 1000 makes that fast enough; the output is single-space separated.

Problem

Input: The first line is an integer n (1 ≤ n ≤ 1000). The second line holds n integers separated by spaces.

Output: The same numbers in non-decreasing order, separated by single spaces.

Samples:

Input	Output
`5 5 3 8 1 9`	`1 3 5 8 9`
`1 42`	`42`
`4 7 7 2 2`	`2 2 7 7`

Sorting in place means the array is rearranged, not copied to a new one. That's why the swap needs a temporary variable — you'll see exactly why in the bug below.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — One pass moves the biggest number to the end

Walk the array comparing each element with the next. If the left one is bigger, swap. After one full pass the largest value has "bubbled" to the last position, because it wins every comparison it takes part in. Do that n−1 times and everything is in order.

Hint 2 — The inner loop gets shorter every round

After i passes, the last i elements are already final. So the inner loop only needs j < n - 1 - i. Without the - i the result is still correct, just wasteful — you'd re-compare a sorted tail over and over.

Hint 3 — A swap is three assignments

int t = a[j]; a[j] = a[j+1]; a[j+1] = t; — and the order matters. The first line exists only to save the value you are about to overwrite. Drop it and the value is gone forever; you'll get a duplicated number and a missing one.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1005];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }

    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

Bubble sort is O(n²) and nobody uses it in production — but it is the clearest demonstration of the two ideas every sorting algorithm shares: compare and swap. Once you've written it by hand, library sorting stops being magic. A worthwhile exercise: add a bool swapped flag, set it on every swap, and break out of the outer loop if a whole pass made no swaps — an already-sorted array then finishes in one pass. From here, stop sorting and start exploiting sortedness in Binary Search.

Deep dive

Why this works

Compare two neighbours and swap when out of order. After one pass the largest has bubbled to the end, because it wins every comparison it takes part in. Repeat n−1 times and everything is ordered.

The cost

O(n²). A thousand numbers means about half a million comparisons where quicksort needs around ten thousand. Its value is pedagogical, not industrial.

Where it goes wrong

Forgetting the temporary in a swap — a[j] = a[j+1]; a[j+1] = a[j]; — sets both slots to the smaller value and the larger one is gone forever.
The inner bound matters: j < n reads a[n] out of bounds, while j < n - 1 is merely slow (it re-compares a sorted tail), not wrong.

Next step

You sorted it so you could use it: Binary Search throws away half the array per step.

Two things to remember

One bubble pass = the largest element lands in place.
A swap is three assignments; the first exists only so you don't lose a value.

🐞 This version fails — open it and try

Swap without a temporary — both slots get the smaller value

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[1005];
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                a[j] = a[j + 1];
                a[j + 1] = a[j];
            }
        }
    }

    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}