/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Random;
import java.util.Scanner;

/* Name of the class has to be "Main" only if the class is public. */
class sorting
{
    public static void show(int [] a){
        for (int i=0; i<a.length; i++) System.out.print(a[i]+" ");

    System.out.println();
    }

    public static void bubbleSort(int [] a){
        int n = a.length;
        int temp = 0;
        for(int i=0; i < a.length; i++){
            for(int j=1; j < (a.length-i); j++){
                if(a[j-1] > a[j]){
                    temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                 }
            }
        }
    }

    public static void InsertionSort(int [] a) {
        int n = a.length;
        for (int j = 1; j < n; j++) {
            int key = a[j];
            int i = j-1;
            while ((i > -1) && ( a[i] > key )) {
                a[i+1] = a[i];
                i--;
            }
            a[i+1] = key;
        }
    }

    public static void SelectionSort(int[] a){
        for (int i=0; i < a.length - 1; i++){
            int index = i;
            for (int j = i + 1; j < a.length; j++){
                if (a[j] < a[index]){
                    index = j;
                }
            }
            int smallerNumber = a[index];
            a[index] = a[i];
            a[i] = smallerNumber;
        }
    }

    public static int Max(int[] a){
        int n=a.length;
        if (n==1) return a[0];
        else if (n==2){
            if (a[0]>a[1]) return a[0];
            else return a[1];}
        else{
            int c = n/2;
            int al[] = new int [c];
            int ar[] = new int [n-c];
            System.arraycopy(a, 0, al, 0, c);
            System.arraycopy(a, c, ar, 0, n-c);
            /*show(a);
            System.out.println();
            show(al);
            System.out.println();
            show(ar);
            System.out.println();
            */
            int maxal=Max(al);
            int maxar=Max(ar);
            if (maxal>maxar) return maxal; else return maxar;
        }
    }


    private static void merge(int a[], int l, int m, int r)
    {
        // sizes of two subarrays
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];

        /*Copy */
        for (int i=0; i<n1; ++i) L[i] = a[l + i];
        for (int j=0; j<n2; ++j) R[j] = a[m + 1+ j];

        /* Merge the temp arrays */
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2){
            if (L[i] <= R[j]){
                a[k] = L[i];
                i++;
            }
            else{
                a[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] AND r[]if any */
        while (i < n1){
            a[k] = L[i];
            i++;
            k++;
        }
        while (j < n2){
            a[k] = R[j];
            j++;
            k++;
        }
    }

    public static void MergeSort(int a[], int l, int r){
        if (l < r){
            int c = (l+r)/2;

            MergeSort(a, l, c);
            MergeSort(a , c+1, r);
            merge(a, l, c, r);
        }
    }

    private static int partition(int a[], int low, int high){
        int pivot = a[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j++)
        {
            if (a[j] <= pivot){
                i++;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = a[i+1];
        a[i+1] = a[high];
        a[high] = temp;

        return i+1;
    }

     public static void QuickSort(int a[], int low, int high){
        if (low < high)
        {
            int pi = partition(a, low, high);
            QuickSort(a, low, pi-1);
            QuickSort(a, pi+1, high);
        }
    }



    public static void main (String[] args) throws java.lang.Exception
    {
        //generate UNsorted array
        //int n=256*256*256*4;  //very big, not recomended to show
        //int n=256*256;  //medium, not to show
        int n=256;  //small, show it
        int data[] = new int [n];
        Random rand = new Random();
        for (int i =0; i < n; i++) data[i]=rand.nextInt(256*256*1285);

        boolean t=true;
        int option;

        Scanner sc=new Scanner(System.in);

        while (t){
          System.out.println();
          System.out.println("1. Bubble Sort");
          System.out.println("2. Insertion Sort");
          System.out.println("3. Selection Sort");
          System.out.println("4. Merge Sort");
          System.out.println("5. Quick Sort");
          System.out.println("6. Find Max");
          System.out.println("0. show array");
          System.out.println("-1. quit");
          System.out.print("your choice > ");
          option=sc.nextInt();

        switch(option){
            case 0: show(data);
                    break;
            case 1: bubbleSort(data);
                    break;
            case 2: //show(data);
                    InsertionSort(data);
                    //show(data);
                    break;
            case 3: //show(data);
                    SelectionSort(data);
                    //show(data);
                    break;
            case 4: //show(data);
                    MergeSort(data,0,data.length-1);
                    //show(data);
                    break;
            case 5: //show(data);
                    QuickSort(data,0,data.length-1);
                    //show(data);
                    break;
            case 6: //show(data);
                    System.out.println("max : " + Max(data));
                    //show(data);
                    break;
            case -1: t=false;
                    break;

                }
            }
        }
}