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.

python3

def insertion_sort(l):
    count = 0
    for i in range(1, len(l)):
        j = i-1 
        key = l[i]
        while (l[j] > key) and (j >= 0):
            
            
            l[j+1] = l[j]
            count +=1
            j -= 1
        l[j+1] = key
    return count

m = input()
l = [int(i) for i in input().strip().split()]

print(insertion_sort(l))

import java.io.; import java.math.; import java.security.; import java.text.; import java.util.; import java.util.concurrent.; import java.util.regex.*;

public class Solution {

// Complete the runningTime function below.
static int runningTime(int[] arr) {
int count=0;
    for(int i=0;i<arr.length ;i++){
        for(int j=0;j<i;j++){
            if(arr[i]<arr[j])
                count++;
        }

        }
  return  count;

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
    BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    int n = scanner.nextInt();
    scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

    int[] arr = new int[n];

    String[] arrItems = scanner.nextLine().split(" ");
    scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

    for (int i = 0; i < n; i++) {
        int arrItem = Integer.parseInt(arrItems[i]);
        arr[i] = arrItem;
    }

    int result = runningTime(arr);

    bufferedWriter.write(String.valueOf(result));
    bufferedWriter.newLine();

    bufferedWriter.close();

    scanner.close();
}

}

In C++ , when we know that the input is in "int" form but they are taking the input in "string vector" form and then they are converting it into "int". Is there any benifits for taking input in vector< string > form?????

I have been banging my head around this, can someone tell me, why my solution is failing 3 testcases python def runningTime(arr): count = 0 for i in range(1, len(arr)): curnum = arr[i] for j in range(i-1, -1,-1): if arr[j] > curnum: arr[j+1] = arr[j] count = count + 1 else: arr[j+1] = curnum break return count

Easy java code

import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;

public class Solution {

static int runningTime(int[] arr) {
    // Complete this function
     int i, key, j,count=0;

for (i = 1; i < arr.length; i++) { key = arr[i]; j = i-1;

   /* Move elements of arr[0..i-1], that are
      greater than key, to one position ahead
      of their current position */
   while (j >= 0 && arr[j] > key)
   {
       arr[j+1] = arr[j];
       j = j-1;
       count++;
   }
   arr[j+1] = key;

} return(count);

}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] arr = new int[n];
    for(int arr_i = 0; arr_i < n; arr_i++){
        arr[arr_i] = in.nextInt();
    }
    int result = runningTime(arr);
    System.out.println(result);
    in.close();
}

}