Last active
February 19, 2019 07:38
-
-
Save jun1st/003177b3f9eddcec58c68189e87109ee to your computer and use it in GitHub Desktop.
Quick Sort Partition
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 int partition(int arr[], int low, int high) { | |
int pivot = arr[high]; | |
// index of smaller element | |
int i = (low -1); | |
for(int j = low; j < high; j++) { | |
if (arr[j] <= pivot) { | |
i++; | |
int temp = arr[i]; | |
arr[i] = arr[j]; | |
arr[j] = temp; | |
} | |
} | |
int temp = arr[i+1]; | |
arr[i+1] = arr[high]; | |
arr[high] = temp; | |
return i + 1; | |
} | |
/* | |
arr[]: array to be sorted | |
low: start index | |
high: end index | |
*/ | |
public static int quickSort(int arr[], int low, int high) { | |
if (low < high) { | |
int pi = partition(arr, low, high); | |
quickSort(arr, low, pi - 1); | |
quickSort(arr, pi + 1, high); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment