Quick Sort

import java.util.Scanner;

public class Quick {
    
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low;
        int j = high;

        while (i < j) {
            while (i <= high && arr[i] <= pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i < j) {
                interchange(arr, i, j);
            }
        }

     
        interchange(arr, low, j);
        return j; 
    }


    public static void interchange(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int j = partition(arr, low, high);
            quickSort(arr, low, j - 1);
            quickSort(arr, j + 1, high);
        }
    }

   
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

    
        System.out.print("Enter the size of the array: ");
        int n = scanner.nextInt();

        
        int[] arr = new int[n];
        System.out.println("Enter " + n + " elements:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

       
        System.out.println("Original array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        
        quickSort(arr, 0, arr.length - 1);

       
        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}




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.


OUTPUT:

Enter the size of the array: 5
Enter 5 elements:
9
3
7
1
5

Original array:
9 3 7 1 5 
Sorted array:
1 3 5 7 9