Quick_Sort_01

import java.util.Arrays;
import java.util.Scanner;

// QUICK SORT

class QuickSort01
{
    /* This function takes last element as pivot,
       places the pivot element at its correct
       position in sorted array, and places all
       smaller (smaller than pivot) to left of
       pivot and all greater elements to right
       of pivot */


    // PARTITIONI -------------------------------------------------------------/////
    int partition(int arr[], int low, int high)
    {
        int pivot = arr[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j++)
        {

            // If current element is smaller than the pivot
            //..............................................
            if (arr[j] < pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                //.......................
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }



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

        return i+1;
    }



    /* The main function that implements QuickSort()
      arr[] --> Array to be sorted,
      low  --> Starting index,
      high  --> Ending index */




    // QUICK SORT -------------------------------------------------------------/////
    void sort(int arr[], int low, int high)
    {
        if (low < high)
        {

            /* pi is partitioning index, arr[pi] is
              now at right place */
            int pi = partition(arr, low, high);


            // Recursively sort elements before
            // partition and after partition
            sort(arr, low, pi-1);
            sort(arr, pi+1, high);
        }
    }




    // UTILITIES --------------------------------------------------------------/////
    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
       // int n = arr.length;
        // for (int i=0; i<n; ++i)
        //    System.out.print(arr[i]+" ");

        System.out.println(Arrays.toString(arr));
    }




    // MAIN program ===========================================================
    public static void main(String args[])
    {
        Scanner input = new Scanner(System.in);
        System.out.print("Input the number of elements : ");
        int N = input.nextInt();


        int arr[] = new int[N];


        for(int a = 0; a < N; a++)
        {
            System.out.printf("Input the [%d] element : ", a);
            arr[a] = input.nextInt();
        }



        int n = arr.length;

        System.out.println();
        System.out.println("Array BEFORE Quick Sort : ");
        printArray(arr);
        System.out.println();


        QuickSort01 sorter = new QuickSort01();

        sorter.sort(arr, 0, n-1);

        // sort(arr, 0, n-1); // If you want to use sort "directly" have to change
        // SORT-method and PARTITION-method to STATIC



        System.out.println("Array AFTER Quick Sort : ");
        printArray(arr);


        input.close();
    }
}