package com.gansuer.algorithms.sort;

/**
 * Created by Frank on 8/2/15.
 */
public class QuickSort extends Sort {

    @Override
    public void sort(Comparable[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSort(arr,0,arr.length-1);
    }

    private void quickSort(Comparable[] arr, int low, int high) {
        if (high <= low) return;

        int mid = partition(arr,low,high);
        quickSort(arr, low, mid - 1);
        quickSort(arr,mid+1,high);
    }


    private int partition(Comparable[] arr, int low, int high){
        int i = low, j = high+1;
        Comparable key = arr[low];
        while (true){
            while (less(arr[++i], key)) if (i==high) break;
            while (less(key,arr[--j])) if (j== low) break;
            if (i >= j) break;
            exchange(arr,i,j);
        }
        exchange(arr,low,j);
        return j;
    }
}

@@ -241,10 +241,12 @@
 arr,
+ 
 0,
+ 
 arr.
@@ -251,17 +251,19 @@
 r.length
--
+ - 
 1);%0A    
@@ -392,25 +392,28 @@
 artition
+X
 (arr,
+ 
 low,
+ 
 high);%0A 
@@ -475,14 +475,18 @@
 arr,
+ 
 mid
-+
+ + 
 1,
+ 
 high
@@ -558,16 +558,17 @@
 nt high)
+ 
 %7B%0A      
@@ -590,17 +590,19 @@
 j = high
-+
+ + 
 1;%0A     
@@ -651,16 +651,17 @@
 e (true)
+ 
 %7B%0A      
@@ -699,18 +699,20 @@
 )) if (i
+ 
 ==
+ 
 high) br
@@ -744,16 +744,17 @@
 ess(key,
+ 
 arr%5B--j%5D
@@ -761,16 +761,17 @@
 )) if (j
+ 
 == low) 
@@ -837,10 +837,12 @@
 arr,
+ 
 i,
+ 
 j);%0A
@@ -872,20 +872,22 @@
 nge(arr,
+ 
 low,
+ 
 j);%0A    
@@ -905,11 +905,575 @@
 j;%0A    %7D
+%0A%0A    private int partitionX(Comparable%5B%5D arr, int low, int high) %7B%0A        Comparable key = arr%5Blow%5D;%0A        while (low %3C high) %7B%0A            while (arr%5Bhigh%5D.compareTo(key) %3E 0 && low %3C high) %7B%0A                high--;%0A            %7D%0A            if (low %3C high) %7B%0A                arr%5Blow++%5D = arr%5Bhigh%5D;%0A            %7D%0A            while (arr%5Blow%5D.compareTo(key) %3C= 0 && low %3C high) %7B%0A                low++;%0A            %7D%0A            if (low %3C high) %7B%0A                arr%5Bhigh--%5D = arr%5Blow%5D;%0A            %7D%0A        %7D%0A        arr%5Blow%5D = key;%0A        return low;%0A    %7D
 %0A%7D%0A

update QuickSort.partition()