public class QuicksortOnly {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {

        int[] arr = {45, 21, 44, 60, 32, 21, 0};

        sort(arr);

        for(int print: arr){

            System.out.print(print + " ");

                           }

    }


    public static void sort(int[] arr){


        quicksort(arr, 0, arr.length - 1);
                                      }


    public static void quicksort(int[] arr, int start, int end){

        if(end - start > 0){

            int p = partition(arr, start, end);
            quicksort(arr, start, p - 1);
            quicksort(arr, p + 1, end);


                           }


                                                               }


public static int partition(int[] arr, int start, int end){

    int pivot = choosePivot(start, end);

    swap(arr, pivot, end);

    int high_border = end - 1;//suspiscious when sorting the right side of the array.
    int low_border = start;

    while(low_border < high_border){

        if(arr[low_border] > arr[end] && arr[high_border] < arr[end]){

            swap(arr, low_border, high_border);
            low_border++;
            high_border--;


                                                                     }

        else if(arr[low_border] > arr[end]){

            high_border--;

                                           }

        else if(arr[high_border] < arr[end]){

            low_border++;

                                            }

        else{


            if(low_border != high_border){
            low_border++;
            high_border--;
                                         }

            }




                                   }
    if(high_border < low_border){
    swap(arr, low_border, end);
                                }

    else if(high_border == low_border){

        if(arr[low_border] > arr[end]){

            swap(arr, low_border, end);
                                      }

                                      }

    return low_border;


                                                          }


//Randomly selects a pivot point between start and end.
public static int choosePivot(int start, int end){

    Random gen = new Random();

    return gen.nextInt((end - start) + 1) + start;


                                                 }

public static void swap(int[] arr, int ind1, int ind2){

    int temp = arr[ind1];

    arr[ind1] = arr[ind2];

    arr[ind2] = temp;
}


}