Bubble Sort

Lab Java Intermediate 20 points

Implement bubble sort with early exit. Print the array after each pass that made swaps, then the total swap count.

Input

n, then n integers.

Output

Passes, then the count.

Example

Input

5
5 1 4 2 8

Output

[1, 4, 2, 5, 8]
[1, 2, 4, 5, 8]
4

Sample input available Sample output available

Editor

Java

Hints

Each pass moves the largest remaining value to the end.

Solution explanation

O(n²) in general, but the early exit makes it O(n) on already-sorted input.

Show solution

import java.util.Arrays;
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();
        int swaps = 0;
        for (int end = n - 1; end > 0; end--) {
            boolean swapped = false;
            for (int i = 0; i < end; i++) {
                if (a[i] > a[i + 1]) {
                    int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
                    swaps++;
                    swapped = true;
                }
            }
            if (!swapped) break;
            System.out.println(Arrays.toString(a));
        }
        System.out.println(swaps);
    }
}

Output

Answer