Quick Sort Implementation in Java

Objective: Write an algorithm to sort an array in increasing or decreasing order using Quick Sort.

Input: An Array arrA[]

Output: A sorted array.

Approach:

Choose any element from the array and call it as pivot element, Example here we have selected middle element as pivot
Place all the elements smaller than pivot in the left side of pivot.
Place all the elements greater than pivot in the right side of pivot.
Sort left side and right side recursively.

Example:

Complete Code:

	public class QuickSort {
	private int[] arrA;

	public QuickSort(int[] arrA) {
	this.arrA = arrA;
	}

	public void quickS(int low, int high) {
	int mid = (low + high) / 2;
	int left = low;
	int right = high;
	int pivot = arrA[mid]; // select middle element as pivot
	while (left <= right) {
	while (arrA[left] < pivot)
	left++;// find element which is greater than pivot
	while (arrA[right] > pivot)
	right—;// //find element which is smaller than pivot
	// System.out.println(arrA[left] + " " + pivot + " " + arrA[right]
	// );
	// if we found the element on the left side which is greater than
	// pivot
	// and element on the right side which is smaller than pivot
	// Swap them, and increase the left and right
	if (left <= right) {
	int temp = arrA[left];
	arrA[left] = arrA[right];
	arrA[right] = temp;
	left++;
	right—;
	}
	}
	// Recursion on left and right of the pivot
	if (low < right)
	quickS(low, right);
	if (left < high)
	quickS(left, high);
	}

	public void display() {
	for (int i = 0; i < arrA.length; i++) {
	System.out.print(" " + arrA[i]);
	}
	}

	public static void main(String[] args) throws java.lang.Exception {
	// your code goes here
	int a[] = { 6, 2, 4, 12, 10 };
	QuickSort i = new QuickSort(a);
	System.out.print("UnSorted : ");
	i.display();
	i.quickS(0, a.length – 1);
	System.out.println("");
	System.out.print("Quick Sorted : ");
	i.display();
	}
	}

Output:
UnSorted : 2 1 8 4 0 9 3 11
Quick Sorted : 0 1 2 3 4 8 9 11

Quick Sort Implementation