package hackerrank;

import java.util.Scanner;

/**
 * https://www.hackerrank.com/challenges/quicksort4
 */
public class RunningTimeOfQuicksort {
    private static int quicksort(int[] array) {
        // TODO:
        return 0;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = in.nextInt();
        }
    }
}

@@ -14,16 +14,41 @@
 rrank;%0A%0A
+import java.util.Arrays;%0A
 import j
@@ -65,16 +65,16 @@
 canner;%0A
-
 %0A/**%0A * 
@@ -200,57 +200,1478 @@
 sort
-(int%5B%5D array) %7B%0A        // TODO:%0A        return 0
+Swaps;%0A    private static int insertionSortShifts;%0A%0A    private static int runningTime(int%5B%5D array) %7B%0A        int%5B%5D copy = Arrays.copyOf(array, array.length);%0A        quicksort(array);%0A        insertionSort(copy);%0A        return insertionSortShifts - quicksortSwaps;%0A    %7D%0A%0A    public static void insertionSort(int%5B%5D ar) %7B%0A        for (int i = 1; i %3C ar.length; i++) %7B%0A            int j = i;%0A            while (j %3E= 1 && ar%5Bj%5D %3C ar%5Bj - 1%5D) %7B%0A                swap(ar, j, j - 1);%0A                j--;%0A                insertionSortShifts++;%0A            %7D%0A        %7D%0A    %7D%0A%0A    private static void quicksort(int%5B%5D array) %7B%0A        quicksort(array, 0, array.length - 1);%0A    %7D%0A%0A    private static void quicksort(int%5B%5D array, int begin, int end) %7B%0A        if (begin %3E= end) %7B%0A            return;%0A        %7D%0A        int p = partition(array, begin, end);%0A        quicksort(array, begin, p - 1);%0A        quicksort(array, p + 1, end);%0A    %7D%0A%0A    private static int partition(int%5B%5D array, int begin, int end) %7B%0A        int pivot = array%5Bend%5D;%0A        int i = begin;%0A        for (int j = begin; j %3C= end - 1; j++) %7B%0A            if (array%5Bj%5D %3C= pivot) %7B%0A                swap(array, i, j);%0A                quicksortSwaps++;%0A                i++;%0A            %7D%0A        %7D%0A        quicksortSwaps++;%0A        swap(array, i, end);%0A        return i;%0A    %7D%0A%0A    private static void swap(int%5B%5D array, int i, int j) %7B%0A        int tmp = array%5Bi%5D;%0A        array%5Bi%5D = array%5Bj%5D;%0A        array%5Bj%5D = tmp
 ;%0A  
@@ -1896,32 +1896,32 @@
 = in.nextInt();%0A
-
         %7D%0A    %7D%0A
@@ -1910,20 +1910,68 @@
 ;%0A        %7D%0A
+        System.out.println(runningTime(array));%0A
     %7D%0A%7D%0A

Solve Running Time of Quicksort