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

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

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.

i used this logic but i am getting error on testcase:6

static int runningTime(int[] arr) {
        int result=0;
        for(int i=0;i<arr.length;i++) {
            for(int j=i+1;j<arr.length;j++) {
                if(arr[i]>arr[j]) {
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                    result++;
                }
            }
        }
        return result;

    }

SOLUTION TO THE PROBLEM:

First , try your level best and then , IF you have any problem : You can visit the link below to have the solution:

https://github.com/Aabhas99/HackerRank-Solution-To-Algorithms

GOOD LUCK!!😊

Javascript solution passed all test cases.

Didn't see what's the catch) Just add one line of code with the counter and the "challenge" is completed .

function processData(input) {
    let counter = 0;
    let arr = input.split("\n")[1].split(' ').map(Number);
    for (let i = 1, j = i; i < arr.length; j = ++i) {
        while (arr[j] < arr[j-1] && j) {
            let temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j--] = temp;
            counter++;
        }
    }    console.log(counter);
}

Doesn't really seem worth 30 points, at least if you follow the suggestion of copying your insertion sort code.

My solution with c#

static int runningTime(int[] arr) {

    int shist=0, aux=0, index=0;

    for (int i=0; i<arr.Length-1; i++){           
         aux=arr[i+1];
         index=i+1;          
         while (index>0){
             if (aux <arr[index-1])
                shist++;
            index--;
         }          
    }
    return shist;

}