xd

import java.util.Random;

public class SzybkieSortowanie {

    public static void bubbleSort(int[] A,int p, int r) {
        int temp = 0;

        for (int i = p; i <= r; i++) {
            for (int j = i+1; j < r; j++) {
                if (A[i] > A[j]) {
                    temp = A[j];
                    A[j] = A[i];
                    A[i] = temp;
                }
            }
        }
    }

    public static int partition(int[] A, int p, int r) {
        int x = A[r];
        int i = p-1;

        for (int j = p; j<=r; j++) {
            if(A[j]<=x) {
                i++;
                int temp = A[i];
                A[i]=A[j];
                A[j]=temp;
            }
        }

        if(i<r) {
            return i;
        }
            return i-1;
    }

    public static void quickSort(int[] A, int p, int r) {
        if(p<r) {
            int q = partition(A,p,r);
            quickSort(A,p,q);
            quickSort(A,q+1,r);
        }
    }

    public static void quickSort2(int[] A, int p, int r) {
        int c = 10;
        if(p<r) {
            if(r - p + 1 < c) {
                bubbleSort(A,p,r);
            } else {
                int q = partition(A,p,r);
                quickSort2(A,p,q);
                quickSort2(A,q+1,r);
            }
        }
    }

    public static int[] randFill(int n) {
        Random random = new Random();
        int[] A = new int[n];
        for (int i = 0; i < n; i++) {
            A[i] = random.nextInt(n+1);
        }

        return A;
    }

    public static void main(String[] args) {
        /*int[] A = {6,1,7,4,3,9,6,3,2,6,5,0,0,1,-8};
        System.out.print("Przed sortowaniem: ");
        for (int x : A) {
            System.out.print(x + " ");
        }
        System.out.print("\nPo sortowaniu: ");
        quickSort2(A,0,A.length-1);
        for (int x : A) {
            System.out.print(x+" ");
        } */

        System.out.println("DANE LOSOWE");
        System.out.println("  rozmiar tablicy   czas - algorytm 1   czas - algorytm 2\n");
        for (int n = 10; n <= 25000; n*=2) {
           int[] A = randFill(n);
           int[] B = A.clone();

           long startTime1 = System.nanoTime();
           quickSort(A,0,B.length-1);
           long endTime1 = System.nanoTime();

           long startTime2 = System.nanoTime();
           quickSort2(A,0,A.length-1);
           long endTime2 = System.nanoTime();

           double totalTime1 = (endTime1-startTime1)/100000000.0;
           double totalTime2 = (endTime2 - startTime2)/100000000.0;
           System.out.format("%17d %19f %19f\n",n,totalTime1,totalTime2);
        }
    }
}