@@ -0,0 +1,2048 @@
+package algorithms.sorting;%0D%0A%0D%0Aimport java.util.*;%0D%0A%0D%0A/*%0D%0A * Problem Statement: %0D%0A * In the previous challenges you created an Insertion Sort algorithm. It is a%0D%0A * simple sorting algorithm that works well with small or mostly sorted data.%0D%0A * However, it takes a long time to sort large unsorted data. To see why, we%0D%0A * will analyze its running time.%0D%0A * %0D%0A * Challenge:%0D%0A * Can you modify your previous Insertion Sort implementation to keep track of%0D%0A * the number of shifts it makes while sorting? The only thing you should print%0D%0A * is the number of shifts made by the algorithm to completely sort the array. A%0D%0A * shift occurs when an element's position changes in the array. Do not shift an%0D%0A * element if it is not necessary.%0D%0A * %0D%0A * Input Format:%0D%0A * The first line contains N, the number of elements to be sorted. The next line%0D%0A * contains N integers a%5B1%5D, a%5B2%5D, ..., a%5BN%5D.%0D%0A * %0D%0A * Output Format:%0D%0A * Output the number of shifts it takes to sort the array.%0D%0A * %0D%0A * Constraints:%0D%0A * 1 %3C= N %3C= 1001%0D%0A * -10000 %3C= x %3C= 10000, x is an element of a%0D%0A * %0D%0A * Sample Input: %0D%0A * 5%0D%0A * 2 1 3 1 2%0D%0A * %0D%0A * Sample Output: %0D%0A * 4%0D%0A */%0D%0Apublic class RunningTimeOfAlgorithms %7B%0D%0A%0D%0A%09public static void insertIntoSorted(int%5B%5D ar) %7B%0D%0A%09%09%0D%0A        int numShifts = 0;%0D%0A        %0D%0A        for (int top = 1; top %3C ar.length; top++) %7B%0D%0A%09%09%09int temp = ar%5Btop%5D;  // copy that item into temp variable%0D%0A%09%09%09int pos = top - 1;%0D%0A            %0D%0A%09%09%09while (pos %3E= 0 && ar%5Bpos%5D %3E temp) %7B%0D%0A%09%09%09%09// move items that are bigger than temp up one position%0D%0A%09%09%09%09ar%5Bpos+1%5D = ar%5Bpos%5D;%0D%0A%09%09%09%09pos--;%0D%0A                numShifts++;%0D%0A%09%09%09%7D%0D%0A%09%09%09ar%5Bpos + 1%5D = temp;  // place temp into last vacated position%0D%0A%09%09%7D%0D%0A        System.out.println(numShifts);%0D%0A%09%7D%0D%0A    %0D%0A    %0D%0A/* Tail starts here */%0D%0A     public static void main(String%5B%5D args) %7B%0D%0A        Scanner in = new Scanner(System.in);%0D%0A        int s = in.nextInt();%0D%0A        int%5B%5D ar = new int%5Bs%5D;%0D%0A         for(int i=0;i%3Cs;i++)%7B%0D%0A            ar%5Bi%5D=in.nextInt(); %0D%0A         %7D%0D%0A         insertIntoSorted(ar);%0D%0A         in.close();%0D%0A    %7D%0D%0A%7D

Add RunningTimeOfAlgorithms