Skip to content

Instantly share code, notes, and snippets.

@unnisworld
Created March 14, 2019 18:09
Show Gist options
  • Save unnisworld/2687e014fdf5d170884bb2b76bd0cea9 to your computer and use it in GitHub Desktop.
Save unnisworld/2687e014fdf5d170884bb2b76bd0cea9 to your computer and use it in GitHub Desktop.
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int arr[] = {11,12,13,14,15,16,17,10};
sort(arr, 0, arr.length-1);
System.out.println("Sorted Array :"+ Arrays.toString(arr));
int arr2[] = {6,5,4,3,2};
sort(arr2, 0, arr2.length-1);
System.out.println("Sorted Array :"+ Arrays.toString(arr2));
}
static void sort(int[] arr, int l, int r) {
if (l < r)
{
int p = partition(arr, l, r);
sort(arr, l, p-1);
sort(arr, p+1, r);
}
}
static int partition(int arr[], int l, int r) {
// Take last element as pivot.
int pivotIndex = r;
int pivot = arr[pivotIndex];
// This is a special variable that will keep track of the first
// element from the left of the array that is greater than the pivot.
int indexOfFirstElementGreaterThanPivot = l;
for(int i=l;i<r;i++) {
if(arr[i] <= pivot) {
// When you find an element smaller than pivot
// exchange it with first element greater than pivot.
swap(arr, i, indexOfFirstElementGreaterThanPivot);
indexOfFirstElementGreaterThanPivot ++;
}
}
// position pivot at the right place by swapping it with
// first element greater than pivot.
swap(arr, indexOfFirstElementGreaterThanPivot, pivotIndex);
int newPivotIndex = indexOfFirstElementGreaterThanPivot;
return newPivotIndex;
}
static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment