/*
 *  You are free to use this code anywhere, copy, modify and redistribute at your
 *  own risk.
 *  Your are solely responsibly for any damage that may occur by using this code.
 *
 *  This code is not tested for all boundary conditions. Use it at your own risk.
 *
 *  Original code: http://www.mycstutorials.com/articles/sorting/quicksort
 */
package com.zhokhov.interview.sorting;

import static com.zhokhov.interview.util.Console.*;

/**
 * @author <a href='mailto:alexey@zhokhov.com'>Alexey Zhokhov</a>
 */
public class QuickSort {

    public void sort(int array[]) {
        quickSort(array, 0, array.length - 1);
    }

    /*
     * The quickSort algorithm implementation
     */
    private void quickSort(int array[], int startIndex, int endIndex) {
        // index of left-to-right scan
        int leftIndex = startIndex;

        // index of right-to-left scan
        int rightIndex = endIndex;

        __grey("\nquickSort, leftIndex: " + leftIndex + ", rightIndex: " + rightIndex + "  ==> ");
        ____purple("" + (endIndex - startIndex >= 1));

        // check that there are at least two elements to sort
        // if there is only one element in the partition, do not do any sorting
        if (endIndex - startIndex >= 1) {
            // set the pivot as the first element in the partition
            int pivot = array[startIndex];

            ____grey("pivot: " + pivot);

            // while the scan indices from left and right have not met
            while (rightIndex > leftIndex) {
                // from the left, look for the first
                // element greater than the pivot
                while (array[leftIndex] <= pivot && leftIndex <= endIndex && rightIndex > leftIndex) {
                    leftIndex++;

                    ____blue(" new leftIndex: " + leftIndex);
                }

                // from the right, look for the first
                // element not greater than the pivot
                while (array[rightIndex] > pivot && rightIndex >= startIndex && rightIndex >= leftIndex) {
                    rightIndex--;

                    ____blue(" new rightIndex: " + rightIndex);
                }

                // if the left seekindex is still smaller than
                // the right index, swap the corresponding elements
                if (rightIndex > leftIndex) {
                    swap(array, leftIndex, rightIndex);
                }
            }

            // after the indices have crossed, swap the last element in
            // the left partition with the pivot
            swap(array, startIndex, rightIndex);

            // quicksort the left partition
            quickSort(array, startIndex, rightIndex - 1);

            // quicksort the right partition
            quickSort(array, rightIndex + 1, endIndex);
        }
    }

    private void swap(int array[], int index1, int index2) {
        ____blue("Swapping: " + index1 + " and " + index2);

        int temp = array[index1];

        array[index1] = array[index2];
        array[index2] = temp;
    }

    public static void main(String[] args) {
        int array[] = {7, 1, 8, 2, 0, 12, 10, 6, 5, 3};

        __yellow("\nNew array: ");
        __dump(array);

        System.out.println("\nSorting");

        QuickSort quickSort = new QuickSort();
        quickSort.sort(array);

        __green("\nResult: ");
        __dump(array);
    }

}

@@ -543,38 +543,160 @@
    p
-ublic void sort(int array%5B%5D) %7B
+rivate int COMPARISONS_COUNT;%0A    private int SWAPS_COUNT;%0A%0A    public void sort(int array%5B%5D) %7B%0A        COMPARISONS_COUNT = 0;%0A        SWAPS_COUNT = 0;%0A
 %0A   
@@ -1181,24 +1181,53 @@
 ex %3E= 1));%0A%0A
+        COMPARISONS_COUNT++;%0A
         // c
@@ -1659,32 +1659,70 @@
  %3E leftIndex) %7B%0A
+                COMPARISONS_COUNT++;%0A%0A
                 
@@ -1903,32 +1903,74 @@
  %3E leftIndex) %7B%0A
+                    COMPARISONS_COUNT++;%0A%0A
                 
@@ -2275,32 +2275,74 @@
 %3E= leftIndex) %7B%0A
+                    COMPARISONS_COUNT++;%0A%0A
                 
@@ -2435,32 +2435,69 @@
              %7D%0A%0A
+                COMPARISONS_COUNT++;%0A
                 
@@ -3195,24 +3195,47 @@
 t index2) %7B%0A
+        SWAPS_COUNT++;%0A
         ____
@@ -3703,24 +3703,24 @@
 Result: %22);%0A
-
         __du
@@ -3729,16 +3729,225 @@
 (array);
+%0A%0A        ____grey(%22%5CnStatistics%22);%0A        __green(%22  Comparisons: %22);%0A        System.out.print(quickSort.COMPARISONS_COUNT);%0A        __green(%22%5Cn  Swaps: %22);%0A        System.out.println(quickSort.SWAPS_COUNT);
 %0A    %7D%0A%0A

Print array changes to console and added statistics in the end of result [Quick Sort].