import java.util.Scanner;

public class QuickSort {
    
    // Method to swap two elements in an array
    public static void interchange(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    // Partition method to select the pivot and arrange the array
    public static int partition(int[] a, int p, int q) {
        int v = a[p];  // pivot element
        int i = p, j = q + 1;
        
        do {
            // Move i to the right as long as the element is less than the pivot
            do {
                i = i + 1;
            } while (i <= q && a[i] < v);
            
            // Move j to the left as long as the element is greater than the pivot
            do {
                j = j - 1;
            } while (a[j] > v && j >= p);
            
            // If i < j, swap the elements
            if (i < j) {
                interchange(a, i, j);
            }
        } while (i < j);
        
        // Swap the pivot with the element at j
        interchange(a, p, j);
        
        return j;  // Return the index of the pivot element
    }
    
    // QuickSort method to recursively sort the subarrays
    public static void quickSort(int[] a, int p, int q) {
        if (p < q) {
            int j = partition(a, p, q);  // Partition the array
            quickSort(a, p, j - 1);       // Sort the left subarray
            quickSort(a, j + 1, q);       // Sort the right subarray
        }
    }

    // Main method to accept input and run the quickSort
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Input size of the array
        System.out.print("Enter Size: ");
        int n = scanner.nextInt();
        
        int[] a = new int[n];  // Array initialization
        
        // Input array elements
        System.out.println("Enter elements: ");
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        // Perform QuickSort
        quickSort(a, 0, n - 1);
        
        // Output the sorted array
        System.out.print("Sorted Array: ");
        for (int i = 0; i < n; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
        
        scanner.close();  // Close the scanner to avoid memory leaks
    }
}




 
Algorithm Partition(a, m, p)
Within a[m], a[m+1],...,a[p-1] the elements are rearranged in such a manner that if initially t = a[m],
then after completion a[q] = t for some q between m and p-1, a[k] < t for m ≤ k < q, and a[k] ≥ t for q < k < p. q is returned. Set a[p] = ∞.
v := a[m]; i := m; j := p;
repeat
    repeat
        i := i + 1;
    until (a[i] ≥ v);
    repeat
        j := j - 1;
    until (a[j] < v);
    if (i < j) then
        Interchange(a, i, j);
} until (i ≥ j);
 
a[m] := a[j]; a[j] := v;
return j;
 
Algorithm Interchange(a, i, j)
// Exchange a[i] with a[j].
temp := a[i];
a[i] := a[j];
a[j] := temp;
 
 
Algorithm: QuickSort (p, q)
 
// Sorts the elements in the array a[p : q] in non-decreasing order.
 
if (p < q) then // If there is more than one element
{
    // Divide the array into two subproblems.
    j := Partition(a, p, q + 1);
    // 'j' is the position of the partitioning element.
 
    QuickSort(p, j - 1); // Sort the left subarray.
    QuickSort(j + 1, q); // Sort the right subarray.