import java.util.Random;

public class BasicTraining {

	/**
	 * Sort the array using quick sort, this must be:
	 *
	 * in-place (no temporary arrays)
	 * O(n log n)
	 *
	 * @param array
	 * @return a sorted array
	 */


	public static <T extends Comparable<? super T>> void quickSortHelper(T[] array) {

        int pivotIndex = 0;
        T pivotObject = array[pivotIndex];
        T temp = array[array.length - 1];
        array[array.length - 1] = array[0];
        array[0] = temp;

        int keepTrack = 0;
        for(int i = 0; i < array.length; i++){
        	if(pivotObject.compareTo(array[i]) > 0){
        		T temp2 = array[keepTrack];
                array[keepTrack] = array[i];
                array[i] = temp2;
                keepTrack = keepTrack + 1;
            }
        }

        T temp3 = array[keepTrack];
        array[keepTrack] = array[array.length - 1];
        array[array.length - 1] = temp3;

	}

	public static <T extends Comparable<? super T>> T[] quickSort(T[] array) {
		for(int i = 0; i < array.length; i++){
			quickSortHelper(array);
		}
		return array;
	}

	public static void main(String[] args) {
        Integer[] arr = {6, 3, 9, 2, 8, 7};
        Integer[] sorted = quickSort(arr);
        for(Integer i : sorted) {
                System.out.println(i);
        }


	}

}