Challenge: Bubble Sort, Pass by Pass

Lab C++ Beginner 10 points

Bubble sort n numbers and print the vector after every pass. Stop as soon as a pass makes no swaps (still print that pass).

Input

Line 1: n (n ≥ 2). Line 2: n whole numbers.

Output

One line per pass.

Example

Input

5
5 1 4 2 8

Output

1 4 2 5 8
1 2 4 5 8
1 2 4 5 8

Sample input available Sample output available

Editor

C++

Hints

Outer loop = passes, inner loop = compare neighbours.

Print after each pass, then stop if nothing swapped.

Solution explanation

The swapped flag makes an already-sorted vector take a single pass.

Show solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    for (int done = 0; done < n - 1; done++) {
        bool swapped = false;
        for (int i = 0; i < n - 1 - done; i++)
            if (v[i] > v[i + 1]) { swap(v[i], v[i + 1]); swapped = true; }
        for (int i = 0; i < n; i++) cout << v[i] << (i + 1 < n ? " " : "\n");
        if (!swapped) break;
    }
    return 0;
}

Output

Answer