Created
May 9, 2019 17:36
-
-
Save stefa168/a7ae6e2605c05f708ede87c5c0b5de43 to your computer and use it in GitHub Desktop.
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 static <E extends Comparable<E>> void quickSort(ArrayList<E> arr, int low, int high) { | |
if (arr == null || arr.size() == 0) | |
return; | |
if (low >= high) | |
return; | |
// pick the pivot | |
int middle = low + (high - low) / 2; | |
E pivotLength = arr.get(middle); | |
// make left < pivot and right > pivot | |
int i = low, j = high; | |
while (i <= j) { | |
while (arr.get(i).compareTo(pivotLength) < 0) { | |
i++; | |
} | |
while (arr.get(j).compareTo(pivotLength) > 0) { | |
j--; | |
} | |
if (i <= j) { | |
E temp = arr.get(i); | |
arr.set(i, arr.get(j)); | |
arr.set(j, temp); | |
i++; | |
j--; | |
} | |
} | |
// recursively sort two sub parts | |
if (low < j) | |
quickSort(arr, low, j); | |
if (high > i) | |
quickSort(arr, i, high); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment