public class PrimerSort {
    /*Функция вывода на экран содержимого массива*/
    private static void printArray(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    /*Функция создания нового массива, заполненого значениями массива,
						переданного в качестве параметра*/
    private static int[] newArray(int[] a) {
        int n = a.length;
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = a[i];
        }
        return b;
    }

    /*Функция перестановки двух элементов массива*/
    private static void swap(int[] a, int i, int j) {
        int x = a[i];
        a[i] = a[j];
        a[j] = x;
    }

    /*Функция для сортировки массива пузырьковой сортировкой*/
    private static int[] bubbleSort(int[] a) {
        int[] b = newArray(a);
        int n = a.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = n - 2; j >= i; j--) {
                if (b[j] > b[j + 1]) {
                    swap(b, j, j + 1);
                }
            }
        }
        return b;
    }

    /*Функция для сортировки массива сортировкой вставками*/
    private static int[] selectionSort(int[] a) {
        int[] b = newArray(a);
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (b[i] > b[j]) {
                    swap(b, i, j);
                }
            }
        }
        return b;
    }

    /*Функция для сортировки массива быстрой сортировкой*/
    private static int[] quickSort(int[] a) {
        int[] b = newArray(a);
        quickSort(b, 0, a.length - 1);
        return b;
    }

    /*перегруженная функция для сортировки массива быстрой сортировкой*/
    private static void quickSort(int[] a, int l, int r) {
        int i = l;
        int j = r;
        int m = (l + r) >> 1;

        while (i <= j) {
            while (a[i] < a[m]) i++;
            while (a[j] > a[m]) j--;
            if (i <= j) {
                swap(a, i, j);

                i++;
                j--;
            }

            if (i < r) quickSort(a, i, r);
            if (j > l) quickSort(a, l, j);
        }
    }

    public static void main(String[] args) {
        /*Создание массива из 20 произвольных целых чисел*/
	int n = 20;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = (int) (Math.random() * 100);
        }

        System.out.print("Array A: ");
        printArray(a);

	/*Вызываем функции для сортировки*/
        int[] bubbleSortArray = bubbleSort(a);
        int[] selectionSortArray = selectionSort(a);
        int[] quickSortArray = quickSort(a);

	/*Выводим получившиеся массивы на экран*/
        System.out.print("bubbleSortArray : ");
        printArray(bubbleSortArray);

        System.out.print("selectionSortArray: ");
        printArray(selectionSortArray);

        System.out.print("quickSortArray: ");
        printArray(quickSortArray);
    }
}