rohangz Can we count the number of shifts ewquired to sort the data i.e number of shifts without actually sorting the data?
brokenmystery 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 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 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 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 How would you suggest doing that in O(n) time.
conkosidowski 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 Awesome, I think what was implied was a method faster than sorting.
RodneyShag 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.
ThatGaggiKid 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 4My 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 I have the same issue as well
edit: I just copied a insertion sort algorithm from online and added the shift variable
ccgrainy 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 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 yeah, tried to micro-optimize. pretty useless on a big scale
oldman09 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 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); }
gursimran16 #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; }
AnastasiaF 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); }
b0kater Doesn't really seem worth 30 points, at least if you follow the suggestion of copying your insertion sort code.
bobcat_12857 Another Python 3 solution...
def runningTime(arr): s = 0 l = { i:x for i,x in enumerate(arr)} for i in range(2,len(arr)+1): x = sorted(arr[:i]) _max = float("-inf") _min = float("inf") c = False for j,n in enumerate(x): if l[j] != n: _max = max(_max,j) _min = min(_min,j) l[j] = n c = True if c: s += _max - _min arr[:i] = x return s
boytsovpanamera Python 3 solution. Tests are passed.
def runningTime(A): N= len(A) total = 0 for i in range(1, N): cnt = 0 while A[i-1] > A[i] and i >0: A[i], A[i-1] = A[i-1], A[i] i-=1 cnt+=1 total +=cnt return total
aurelian_ioan90 This is my submission in C++11.
int runningTime(vector<int> arr) { int i{0}, j{0}, value{0}, count{0}; for (i = 1; i < arr.size(); i++) { value = arr[i]; j = i; while (j > 0 && value < arr[j - 1]) { arr[j] = arr[j - 1]; j = j - 1; count++; } arr[j] = value; } return count++; }
adithyamandarthi //c++ solution
int runningTime(vector<int> arr) { int count = 0; for(int i=1;i<arr.size();i++) { int x = arr[i]; for(int j=i-1;j>=0;j--) { if(arr[j] > x) { count++; arr[j+1] = arr[j]; if(j==0) arr[j] = x; } else { arr[j+1] = x; break; } } } return count; }
Sort 110 Discussions, By:
Please Login in order to post a comment