/*
 * [QuickSort.java]
 *
 * Summary: Tony Hoare's QuickSort in Java.
 *
 * Copyright: (c) 1996-2017 Roedy Green, Canadian Mind Products, http://mindprod.com
 *
 * Licence: This software may be copied and used freely for any purpose but military.
 *          http://mindprod.com/contact/nonmil.html
 *
 * Requires: JDK 1.8+
 *
 * Created with: JetBrains IntelliJ IDEA IDE http://www.jetbrains.com/idea/
 *
 * Version History:
 *  1.0 1998-01-01 initial version
 *  1.1 1998-11-10 add name and address.
 *  1.2 1998-12-28 JDK 1.2 style Comparator
 *  1.3 2002-02-19 java.util.Comparator by default.
 *  1.4 2002-03-30 tidy code.
 *  1.5 2003-05-30 add dummy private constructor
 *  1.6 2008-01-01 add generics to comparator
 */
package com.mindprod.quicksort;

import java.util.Comparator;

import static java.lang.System.*;

/**
 * Tony Hoare's QuickSort in Java.
 * <p/>
 * Eric van Bezooijen <eric@logrus.berkeley.edu> was the
 * original author of this version of QuickSort.  I modified
 * the version he posted to comp.lang.java to use a callback
 * delegate object. I also made a few optimisations.
 * <p/>
 * I have also posted source for HeapSort and RadixSort both
 * of which run faster than QuickSort.
 *
 * @author Roedy Green, Canadian Mind Products
 * @version 1.6 2008-01-01 add generics to comparator
 * @since 1998
 */
public class QuickSort<T>
    {
    private static final boolean DEBUGGING = false;

    private static final int FIRST_COPYRIGHT_YEAR = 1996;

    private static final String EmbeddedCopyright =
            "Copyright: (c) 1996-2017 Roedy Green, Canadian Mind Products, http://mindprod.com";

    /**
     * when package released.
     *
     * @noinspection UnusedDeclaration
     */
    private static final String RELEASE_DATE = "2008-01-01";

    /**
     * embedded version string.
     */
    @SuppressWarnings( { "UnusedDeclaration" } )
    private static final String VERSION_STRING = "1.6";

    // callback object we are passed that has
    // a Comparator( <? super T> a, <? super T> b ) method.
    private Comparator<? super T> comparator;

    // pointer to the array of user's objects we are sorting
    private T[] userArray;

    /**
     * dummy constructor to prevent its use. Use static method sort.
     */
    private QuickSort()
        {
        }

    // check if user's array is already sorted
    private boolean isAlreadySorted()
        {
        for ( int i = 1; i < userArray.length; i++ )
            {
            if ( comparator.compare( userArray[ i ], userArray[ i - 1 ] ) < 0 )
                {
                return false;
                }
            }
        return true;
        } // end isAlreadySorted

    // Partition by splitting this chunk to sort in two and
    // get all big elements on one side of the pivot and all
    // the small elements on the other.
    private int partition( int lo, int hi )
        {
        // If set were unsorted lo is as good as any other a guess at a suitable mid point.
        // If set were almost sorted, (lo+hi/2) would be a better guess.
        // I have left it as it was in the original.
        T pivot = userArray[ lo ];
        while ( true )
            {
            // A specialised sort for strings might avoid comparing the the first few common chars to all
            // Strings in the partition.
            while ( comparator.compare( userArray[ hi ], pivot ) >= 0 &&
                    lo < hi )
                {
                hi--;
                }
            while ( comparator.compare( userArray[ lo ], pivot ) < 0 &&
                    lo < hi )
                {
                lo++;
                }
            if ( lo < hi )
                {
                // exchange objects on either side of the pivot
                T temp = userArray[ lo ];
                userArray[ lo ] = userArray[ hi ];
                userArray[ hi ] = temp;
                }
            else
                {
                return hi;
                }
            } // end while
        } // end partition

    // recursive quicksort that breaks array up into sub
    // arrays and sorts each of them.
    private void quicksort( int p, int r )
        {
        if ( p < r )
            {
            int q = partition( p, r );
            if ( q == r )
                {
                q--;
                }
            quicksort( p, q );
            quicksort( q + 1, r );
            } // end if
        } // end quicksort

    /**
     * sort the user's array
     *
     * @param userArray  Array of Objects to be sorted.
     * @param comparator Comparator delegate that can compare two Objects and tell which should come first.
     */
    public static <T> void sort( T[] userArray, Comparator<? super T> comparator )
        {
        QuickSort<T> h = new QuickSort<>();
        h.comparator = comparator;
        h.userArray = userArray;
        if ( h.isAlreadySorted() )
            {
            return;
            }
        h.quicksort( 0, userArray.length - 1 );
        if ( h.isAlreadySorted() )
            {
            return;
            }
        if ( DEBUGGING )
            {
            // debug ensure sort is working
            if ( !h.isAlreadySorted() )
                {
                out.println( "Sort failed" );
                }
            }
        } // end sort
    } // end class QuickSort