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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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