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.

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

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

this uses same concept of invariant as larry's array question

int i,j,k;
for(i=1;i<=n-1;i++)
{ 
    for(j=0;j<=i;j++)
    {
       while(arr[j]>arr[i])
        {

            int temp2=arr[i];
            arr[i]=arr[j];
            arr[j]=temp2;

        }
    }
    for(k=0;k<=n-1;k++)
    printf("%d ",arr[k]);
    printf("\n");

}

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!!😊

static int runningTime(int[] a) {
        int i, j, key, shifts = 0;
        for (j = 1; j < a.length; j++) {
            key = a[j];
            i = j-1;
            while (i >= 0 && a[i] > key) {
                a[i+1] = a[i];
                i = i-1;
                shifts++;
            }
            a[i+1] = key;
        }
        return shifts;
    }

Here is my code. It passes all the testcases but few of them take too much time. Is it because of O(N^2) time complexity?

JavaScript Solution

arr.reduce((p,c,i) => {
    let num = i - 1;
    while (num >= 0) {
      if (arr[num] > c) p += 1;
      num --;
    }
    return p;
  }, 0);