# Running Time of Algorithms

# Running Time of Algorithms

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

brokenmystery + 1 comment YES WE CAN... simply count the number of inversions in the array for each element. Because the number of shifts required is equal to the number of inversions in the original array

conkosidowski + 1 comment Ah, thank you. I have to admit I had to look up inversion count.

Basically just count every time an element with a higher index is smaller than an element with a lower index.

Bad_Jim + 2 comments Interesting. It seems that the fast way to count inversions is to do a merge sort and count inversions while merging. It can also be done with trees. But the methods all seem to have some kind of sorting in common. So the answer to rohangz question is probably "no".

sfelde21 + 1 comment he just said you can count inverstions by incrementing every time a higher index is smaller than a lower index. merge sort is most definitely not the answer

AffineStructure + 1 comment How would you suggest doing that in O(n) time.

conkosidowski + 1 comment It's not that it's in O(n) time, but you don't need to sort. I think the final result can be, at the least, O(n^2).

AffineStructure + 0 comments Awesome, I think what was implied was a method faster than sorting.

RodneyShag + 0 comments ### 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.

gursimran16 + 0 comments #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> int insertionsort(int *a,int n) { int i; int value; int hole; int shift=0; for(i=1;i<n;i++) { value=a[i]; hole=i; while(hole>0 && a[hole-1]>value) { a[hole]=a[hole-1]; hole=hole-1; shift++; } a[hole]=value; } return shift; } int main() { int n; int *a; int i; scanf("%d",&n); a=(int*)malloc(sizeof(int)*n); for(i=0;i<n;i++) scanf("%d",(a+i)); printf("%d",insertionsort(a,n)); return 0; }

ThatGaggiKid + 4 comments 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

phoenix786 + 0 comments I have the same issue as well

edit: I just copied a insertion sort algorithm from online and added the shift variable

ccgrainy + 0 comments How do you move the three at index 2 to index 0 in 1 shift? I think maybe there is a confusion with what a shift is.

As I understood it a shift is moving an element of an array one position to the left. In this example you have to move 3 to positions to the left, and therefor two shifts.

jeffburtjr + 3 comments Sounds like you're not doing a true insertion sort. In order it to be a true insertion sort, you have to move that 3 to the left two times. I.e.: "4 3 4 4" then "3 4 4 4".

ThatGaggiKid + 0 comments yeah, tried to micro-optimize. pretty useless on a big scale

oldman09 + 0 comments Does whether it is a true insertion sort really matter? Their time complexity are both O(n^2) aren't they? Just a different inner loop directionÂ¯_(ãƒ„)_/Â¯

m_viey + 0 comments The solution with swap instead shift passes all tests and optimize this case. So I keep it and go forward.

use std::io; fn main() { let reader = io::stdin(); let mut input = String::new(); reader.read_line(&mut input).expect("fail to readline"); let size = input.trim().parse::<usize>().expect("not a number"); let mut values = Vec::with_capacity(size); let mut count = 0; input.clear(); reader.read_line(&mut input).expect("fail to readline"); for value in input.split_whitespace() { values.push(value.parse::<i32>().expect("not a number")); } for i in 1 .. values.len() { for j in 0 .. i { if values[i] < values[j] { let tmp = values[i]; values[i] = values[j]; values[j] = tmp; count += 1; } } } println!("{}", count); }

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

314sahil + 0 comments this uses same concept of invariant as larry's array question

agarwalvibhor930 + 0 comments `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"); }`

Aabhas99 + 0 comments *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!!ðŸ˜Š*

riteshbehera123 + 0 comments 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?

vldvel + 0 comments JavaScript Solution

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

Sort 104 Discussions, By:

Please Login in order to post a comment