Java QuickSort Example
Chapter:
Interview Programs
Last Updated:
05-11-2016 13:18:24 UTC
Program:
/* ............... START ............... */
public class JavaQuickSort {
private int array[];
private int length;
public void sortElements(int[] arrayvalues) {
if (arrayvalues == null || arrayvalues.length == 0) {
return;
}
this.array = arrayvalues;
length = arrayvalues.length;
doQuickSort(0, length - 1);
}
private void doQuickSort(int lowIndex, int highIndex) {
int i = lowIndex;
int j = highIndex;
int pivot = array[lowIndex + (highIndex - lowIndex) / 2];
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapElements(i, j);
i++;
j--;
}
}
if (lowIndex < j) {
doQuickSort(lowIndex, j);
}
if (i < highIndex) {
doQuickSort(i, highIndex);
}
}
private void swapElements(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String a[]) {
JavaQuickSort quicksort = new JavaQuickSort();
int[] inputarray = { 32, 1, 23, 14, 43, 7, 6, 65 };
System.out.println("Before sorting");
for (int i : inputarray) {
System.out.print(i);
System.out.print(" ");
}
quicksort.sortElements(inputarray);
System.out.println("After sorting");
for (int i : inputarray) {
System.out.print(i);
System.out.print(" ");
}
}
}
/* ............... END ............... */
Output
Before sorting
32 1 23 14 43 7 6 65 After sorting
1 6 7 14 23 32 43 65
Notes:
-
Quick sort uses divide and conquer algorithm.
- First will be divided in to two parts based on some pivot element. All elements which are less than pivot element will be placed left and and all elements which are greater than pivot will be in right part.
- So now pivot element is exactly in middle. if we sort left and right side elements all elements will be sorted. Here recursive quick sort will take place in order to sort all elements.
- Quick sort will be sorting these elements without using extra space that is the reason it is called in place sorting algorithm.
- Using the first or middle elements as an pivot element. it splits the arrays by re arranging the elements like every thing that is less than pivot will come left side and all elements greater than or equal to pivot will come right side.
- Now pivot is in middle and correct place it left and right arrays sorted then entire array will be sorted.
- Quick sort exactly will do the same it will sort left and right recursively.
- If size of input is very less merge sort will be time consuming.
- For smaller inputs quick sort is faster than merge sort.
- Time complexity of Quicksort default case is O(n log n).
- Worst case Time complexity of Quicksort is O(n2).
Tags
QuickSort Example, Java, Interview Programs