Quick_Sort_02

import java.util.Scanner;

public class QuickSort02
{

    private int array[];
    private int length;




    // sort ...................................................................
    public void sort(int[] inputArr)
    {

        if (inputArr == null || inputArr.length == 0)
        {
            return;
        }

        this.array = inputArr;
        this.length = inputArr.length;

        quickSort(0, length - 1);
    }




    // QuickSort...............................................................
    private void quickSort(int lowerIndex, int higherIndex)
    {

        int i = lowerIndex;
        int j = higherIndex;


        // calculate pivot number, I am taking pivot as middle index number
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];


        // Divide into two arrays
        while (i <= j) {

            /*
             * In each iteration, we will identify a number from left side which
             * is greater then the pivot value, and also we will identify a number
             * from right side which is less then the pivot value. Once the search
             * is done, then we exchange both numbers.

             * При всяка итерация намираме числото от ДЯСНО, което е по-голямо
             * от главния (pivot) елемента и също намираме числото от ЛЯВО,
             * което е по-малко от главния елемнт.
             * След като приключим с търсенето разменяме местата на двата елемента
             *
             */

            while (array[i] < pivot)
            {
                i++;
            }

            while (array[j] > pivot)
            {
                j--;
            }


            if (i <= j)
            {
                exchangeNumbers(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }



        // call quickSort() method RECURSIVELY
        if (lowerIndex < j)
            quickSort(lowerIndex, j);

        if (i < higherIndex)
            quickSort(i, higherIndex);
    }



    // Exchange numbers .......................................................
    private void exchangeNumbers(int i, int j)
    {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }



    // MAIN ////////////////////////////////////////////////////////////////////
    public static void main(String args[])
    {

        QuickSort02 sorter = new QuickSort02();


        Scanner sc = new Scanner(System.in);
        System.out.print("Input the number of elements : ");
        int N = sc.nextInt();


        int arr[] = new int[N];

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


        System.out.println();
        // Print before sorting................................................
        System.out.println("Before Sorting : ");
        for(int i:arr)
        {
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println();


        sorter.sort(arr);


        System.out.println();
        // Print after sorting.................................................
        System.out.println("After Sorting : ");
        for(int i:arr)
        {
            System.out.print(i);
            System.out.print(" ");
        }

        sc.close();
    }
}