Last active
November 22, 2015 13:28
QuickSort implementation in Java
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
// All credits for this implementation go to Java2Novice | |
// http://java2novice.com/java-sorting-algorithms/quick-sort/ | |
public class MyQuickSort { | |
private int array[]; | |
private int length; | |
public void sort(int[] inputArr) { | |
if (inputArr == null || inputArr.length == 0) { | |
return; | |
} | |
this.array = inputArr; | |
length = inputArr.length; | |
quickSort(0, length - 1); | |
} | |
private void quickSort(int lowerIndex, int higherIndex) { | |
int i = lowerIndex; | |
int j = higherIndex; | |
// calculate pivot number, I am taking pivot as middle index number | |
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2]; | |
// Divide into two arrays | |
while (i <= j) { | |
/** | |
* In each iteration, we will identify a number from left side which | |
* is greater then the pivot value, and also we will identify a number | |
* from right side which is less then the pivot value. Once the search | |
* is done, then we exchange both numbers. | |
*/ | |
while (array[i] < pivot) { | |
i++; | |
} | |
while (array[j] > pivot) { | |
j--; | |
} | |
if (i <= j) { | |
exchangeNumbers(i, j); | |
//move index to next position on both sides | |
i++; | |
j--; | |
} | |
} | |
// call quickSort() method recursively | |
if (lowerIndex < j) | |
quickSort(lowerIndex, j); | |
if (i < higherIndex) | |
quickSort(i, higherIndex); | |
} | |
private void exchangeNumbers(int i, int j) { | |
int temp = array[i]; | |
array[i] = array[j]; | |
array[j] = temp; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment