Challenge: Watch the Bubbles

Lab Java Beginner 10 points

Bubble sort the numbers (smallest first). After each pass print the array, separated by spaces. Stop as soon as a pass makes no swaps (that pass is still printed), or after n − 1 passes. Finally print passes: <k>.

Input

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

Output

One line per pass, then passes: k.

Example

Input

5
5 1 4 2 8

Output

Sample input available Sample output available

Editor

Java

Hints

Inner loop: i from 0 to n - pass - 1, swap when a[i] > a[i + 1].

Print after every pass, then break if nothing was swapped.

Solution explanation

On sorted input it stops after one pass. On reversed input it needs all n − 1 passes – the O(n²) worst case.

Show solution

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        int passes = 0;
        for (int pass = 1; pass < n; pass++) {
            boolean swapped = false;
            for (int i = 0; i < n - pass; i++) {
                if (a[i] > a[i + 1]) {
                    int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
                    swapped = true;
                }
            }
            passes++;
            for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(a[i]);
            sb.append('\n');
            if (!swapped) break;
        }
        sb.append("passes: ").append(passes);
        System.out.println(sb);
    }
}

Output

Answer