| 18 | } |
| 19 | |
| 20 | public static int partition(int arr[], int si, int ei) { |
| 21 | int pivot = arr[ei]; |
| 22 | int i = si-1; // makes space for elements smaller than pivot |
| 23 | |
| 24 | for(int j=si; j<ei; j++) { |
| 25 | if(arr[j] < pivot) { |
| 26 | i++; |
| 27 | //swap |
| 28 | int temp = arr[i]; |
| 29 | arr[i] = arr[j]; |
| 30 | arr[j] = temp; |
| 31 | } |
| 32 | } |
| 33 | |
| 34 | //place pivot at correct position |
| 35 | i++; |
| 36 | int temp = arr[i]; |
| 37 | arr[i] = pivot; |
| 38 | arr[ei] = temp; //pivot's position need to change so (pivot = temp) won't work |
| 39 | |
| 40 | return i; |
| 41 | } |
| 42 | public static void main(String args[]) { |
| 43 | int arr[] = {6, 3, 9, 5, 2, 8}; |
| 44 | quickSort(arr, 0, arr.length-1); |