Hey, I got marked off because my sorting algorithm sorts using one less shift. It passed all the test cases except the last one because it sorts it using 1 less sort than your solution.

My Code import java.util.; import java.io.; public class InsertionSort { public static void main(String[] arg) { // check how many items we have Scanner sc = new Scanner(System.in); int nums = sc.nextInt();

        if (nums == 0)
                return;

        // get the unsorted integers into an array
        int[] array = new int[nums];
        for (int i = 0; i < nums; i++)
                array[i] = sc.nextInt();

        // call the insertion sort mehtod
        insertionSort(array);
    }

    public static void insertionSort(int[] array)
    {
        int totalShifts = 0;
        int nSorted = 1; // the first n items are sorted
        int n = array.length; // total number of items in the array
        while (nSorted < n)
        {
                // get the next item
                int newInt = array[nSorted];
                int i = 0;
                // locate its position in smaller array
                for (i = 0; i < nSorted; i++)
                    // if you find a smaller item in there, exchange the two
                    if (array[i] > newInt)
                    {
                        array[nSorted] = array[i];
                        array[i] = newInt; 
                        // make sure exchanging the two didnt make a new imbalance, continue searching through
                        newInt = array[nSorted];
                                    totalShifts++;
                    }
                nSorted++;
        }
        // print total number of shifts
        System.out.print(totalShifts);
    }
}

The test case:

4
4 4 3 4

My solutions output: 1

The test case's output: 2

Lost 5 hackos because my algorithm is more optimal :/ and gets the job done just as well

Can we count the number of shifts ewquired to sort the data i.e number of shifts without actually sorting the data?

Java solution - passes 100% of test cases

From my HackerRank solutions.

import java.util.Scanner;

public class Solution {

    public static void insertionSortShiftCounter(int[] array) {
        int shifts = 0;
        for (int i = 1; i < array.length; i++) {
            int j = i;
            int value = array[i];
            while (j >= 1 && array[j-1] > value) {
                array[j] = array[j-1];
                j--;
                shifts++;
            }
            array[j] = value;
        }
        System.out.println(shifts);
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int s = scan.nextInt();
        int[] array = new int[s];
        for (int i = 0; i < s; i++) {
            array[i] = scan.nextInt(); 
        }
        insertionSortShiftCounter(array);
    }
}

Let me know if you have any questions.

Python 3:

def runningTime(arr):
    count = 0
    for j in range(len(arr)):
        for i in range(j, len(arr)):
            if arr[j] > arr[i]:
                count += 1
    return count