JetBrains Academy: Insertion sort in Java - Kamil-Jankowski/Learning-JAVA GitHub Wiki

JetBrains Academy: Insertion sort in Java

The number of required shifts:

Write a program that counts the number of required shifts to sort the numbers in the descending order using insertion sort.

By shift, we mean the case when we move elements in the sorted part to insert a new element. Another case is when a new element is added to the end of the sorted part without any shifts.

The following picture shows both the cases. We do not need any shifts to add 21 to the sorted part, but we must perform a shift to insert 24 in the sorted part.

Do not count the number of exchanges. You should count only the number of required shifts. An iteration may contain no more than one shift.

Input data format: The first line contains the number of elements. The second line consists of elements separated by space.

Output data format: Output one integer number - the number of required shifts.

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        scanner.nextLine();
        int[] array = Arrays.stream(scanner.nextLine().split("\\s+"))
                            .mapToInt(Integer::parseInt)
                            .toArray();
        int result = countShifts(array);

        System.out.println(result); 
    }
    
    public static int countShifts(int[] array) {
        int shifts = 0;

        /* iterating over elements in the unsorted part */
        for (int i = 1; i < array.length; i++) {
            int elem = array[i]; // take the next element
            int j = i - 1;

            /* find a suitable position to insert and shift elements to the right */
            while (j >= 0 && array[j] < elem) {
                array[j + 1] = array[j]; // shifting
                j--;
                if (j < 0 || array[j] >= elem) {
                    shifts++;
                }
            }
            array[j + 1] = elem; // insert the element in the found position in the sorted part

        }
        return shifts;
    }
}

---