【HackerRank】Running Time of Quicksort

Challenge
In practice, how much faster is Quicksort (in-place) than Insertion Sort? Compare the running time of the two algorithms by counting how many swaps or shifts each one takes to sort an array, and output the difference. You can modify your previous sorting code to keep track of the swaps. The number of swaps required by Quicksort to sort any given input have to be calculated. Keep in mind that the last element of a block is chosen as the pivot, and that the array is sorted in-place as demonstrated in the explanation below.

Any time a number is smaller than the partition, it should be "swapped", even if it doesn't actually move to a different location. Also ensure that you count the swap when the pivot is moved into place. The count for Insertion Sort should be the same as the previous challenge, where you just count the number of "shifts".

Input Format
There will be two lines of input:

n - the size of the array
ar - n numbers that makes up the array

Output Format
Output one integer D, where D = (insertion sort shifts) - (quicksort swaps)

Constraints
1<=s<=1000
-1000<=x<= 1000 , x ∈ ar

Sample Input

7
1 3 9 8 2 7 5

Sample Output

Explanation
Insertion Sort will take 9 "shifts" to sort the array. Quicksort will take 8 "swaps" to sort it, as shown in the diagram below. 9-8 = 1, the output.

题解：统计排序中快速排序和插入排序元素移动次数的差。对于插入排序，统计元素移动的次数；对于快速排序统计元素交换的次数（包括自己跟自己交换），然后输出二者之差。

对于插入排序元素的移动次数可以参见：Insertion Sort Advanced Analysis，不过这道题暴力可能也可以过，有现成的代码就拿来用了。

对于快速排序，直接在排序过程中统计交换次数就可以了，上述引自HackerRank的图很好的说明了快速排序中Partition的工作过程。

最终代码如下：

  1 import java.util.*;
  2 
  3 public class Solution {
  4     private static long answer = 0;
  5     private static long swaps = 0;
  6     private static void swap(int[] ar,int i,int j){
  7         swaps++;
  8         int temp = ar[i];
  9         ar[i] = ar[j];
 10         ar[j]= temp;
 11         return;
 12     }
 13     private static int Partition(int[] ar,int start,int end){
 14         int pivot = ar[end];
 15         int i = start;
 16         int j = start;
 17         while(i<end){
 18             if(ar[i]< pivot ){
 19                 swap(ar,i,j);
 20                 i++;
 21                 j++;
 22             }
 23             else {
 24                 i++;
 25             }
 26         }
 27         swap(ar,j, end);
 28         return j;
 29     }
 30     
 31     private static void quickSort(int[] ar,int start,int end){
 32         if(start >= end)
 33             return;
 34         int pivot = Partition(ar,start,end);
 35         quickSort(ar,start,pivot-1);
 36         quickSort(ar, pivot+1, end);
 37     }
 38     private static int[] Merge(int[] ar1,int[] ar2){
 39         int m = ar1.length;
 40         int n = ar2.length;
 41         
 42         int point1 = 0;
 43         int point2 = 0;
 44         int index_result = 0;
 45         int[] result = new int[m+n];
 46         while(point1 < m && point2 < n){
 47             if(ar1[point1] < ar2[point2]){
 48                 result[index_result] = ar1[point1];
 49                 point1++;
 50                 index_result++;
 51             }
 52             else if(ar1[point1] > ar2[point2]){
 53                 answer += m - point1;
 54                 result[index_result] = ar2[point2];
 55                 index_result++;
 56                 point2++;
 57             }
 58             else{
 59                 result[index_result] = ar1[point1];
 60                 index_result++;
 61                 point1++;
 62             }
 63         }
 64         while(point1 < m){
 65             result[index_result] = ar1[point1];
 66             index_result++;
 67             point1++;
 68         }
 69         while(point2 < n){
 70             answer += m - point1;
 71             result[index_result] = ar2[point2];
 72             index_result++;
 73             point2++;
 74         }
 75         return result;
 76     }
 77     private static int[] mergeSort(int[] ar){
 78         int n = ar.length;
 79         if(n <= 1)
 80             return ar;
 81         int mid = n/2;
 82         int[] ar1 = new int[mid];
 83         int[] ar2 = new int[n-mid];
 84         System.arraycopy(ar, 0, ar1, 0, mid);
 85         System.arraycopy(ar, mid, ar2, 0, n-mid);
 86         int[] sorted_ar1 = mergeSort(ar1);
 87         int[] sorted_ar2 = mergeSort(ar2);
 88         int[] result = Merge(sorted_ar1, sorted_ar2);
 89         return result;
 90     }
 91     public static void main(String[] args) {
 92         
 93         Scanner in = new Scanner(System.in);
 94         int n = in.nextInt();
 95         int[] ar = new int[n];
 96         int[] arr = new int[n];
 97         for(int i = 0;i < n;i++){
 98             ar[i] = in.nextInt();
 99             arr[i]= ar[i];
100         }
101         mergeSort(arr);
102         quickSort(ar, 0, ar.length-1);
103         System.out.println(answer - swaps);
104     }
105 }