Challenge: Count the Shifts

Lab Java Intermediate 20 points

Sort the numbers with insertion sort and count how many times an item is shifted one place to the right. Print the sorted numbers, then the number of shifts. (The shift count tells you how “unsorted” the data was.)

Input

Line 1: n. Line 2: n whole numbers.

Output

Line 1: the sorted numbers. Line 2: shifts: <s>.

Example

Input

5
7 3 9 5 1

Output

1 3 5 7 9
shifts: 7

Sample input available Sample output available

Editor

Java

Hints

Add 1 every time the while loop moves an item right.

Use a[j] > card (not >=) so equal numbers don't move.

Solution explanation

Sorted input needs 0 shifts (O(n) total work); reversed input needs n(n−1)/2 shifts (O(n²)).

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();
        long shifts = 0;
        for (int i = 1; i < n; i++) {
            int card = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > card) {
                a[j + 1] = a[j];
                j--;
                shifts++;
            }
            a[j + 1] = card;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(a[i]);
        System.out.println(sb);
        System.out.println("shifts: " + shifts);
    }
}

Output

Answer