Insertion Sort

Lab Java Intermediate 20 points

Implement insertion sort and print the array after inserting each element (from the second one).

Input

n, then n integers.

Output

n − 1 lines.

Example

Input

5
4 3 5 1 2

Output

[3, 4, 5, 1, 2]
[3, 4, 5, 1, 2]
[1, 3, 4, 5, 2]
[1, 2, 3, 4, 5]

Sample input available Sample output available

Editor

Java

Hints

Shift bigger elements right, then drop the key into the gap.

Solution explanation

Insertion sort is fast for small or nearly-sorted arrays - Java's own sort uses it for tiny ranges.

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();
        for (int i = 1; i < n; i++) {
            int key = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > key) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = key;
            System.out.println(Arrays.toString(a));
        }
    }
}

Output

Answer