Running Time of Algorithms
Running Time of Algorithms
+ 7 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
+ 2 comments Python 3:
def runningTime(arr): count = 0 for j in range(len(arr)): for i in range(j, len(arr)): if arr[j] > arr[i]: count += 1 return count
+ 1 comment Can we count the number of shifts ewquired to sort the data i.e number of shifts without actually sorting the data?
+ 1 comment #python3 def runningTime(arr): z=0 if arr==sorted(arr): return (0) else: for i in range(1,len(arr)): x=arr[i] for j in range(i): if arr[j]>x: (arr[i],arr[j])=(arr[j],arr[i]) z+=1 return z
+ 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.
Sort 216 Discussions, By:
Please Login in order to post a comment