/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package sort;

import java.util.Random;

/**
 *
 * @author Martijn
 */
public class Sort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Sort s = new Sort();
        int array[] = randomIntArray(69000, 10);
        System.out.println("Started");
        //long Start = System.currentTimeMillis();
        s.sort(array);
        //long End = System.currentTimeMillis();
        for(int i = 0; i< array.length; i++){
            System.out.println(array[i]);
        }
        //long Finish = End - Start;
        //System.out.println("Finished in:" +Finish);
    }
    public static int[] randomIntArray(int length, int n)
    {
        int[] a = new int[length];
        Random generator = new Random();
        // for each item in the list
        for (int i = 0; i < a.length; i++)
        {
          // create a new random number and populate the
          // current location in the list with it
          a[i] = generator.nextInt(n);
        }
        return a;
    }
    public void sort(int[] A)
    {
        quickSort(A,0,A.length-1);
    }

    public void quickSort(int[] A,int left,int right)
    {
        if(left < right)
        {
            int pi = partition(A,left,right);
            quickSort(A,left,pi-1);
            quickSort(A,pi+1,right);
        }
    }
    public int partition(int[] A,int left,int right)
    {
        int i = left-1;
        int j = left-1;
        do {
            j++;
            if (A[j] <= A[right])
            {
                i++;
                swap(A,i,j);
            }
        }
        while (j < right - 1);
        swap(A,i+1, right);
        return i + 1;
    }

    public void swap(int[] A, int x, int y)
    {
        int z = A[x];
        A[x] = A[y];
        A[y] = z;
    }
}