Skip to content

Instantly share code, notes, and snippets.

@YusufAbdelaziz
Created March 28, 2020 17:14
Show Gist options
  • Save YusufAbdelaziz/4f0d83b07be99f595aea03f19e269f8d to your computer and use it in GitHub Desktop.
Save YusufAbdelaziz/4f0d83b07be99f595aea03f19e269f8d to your computer and use it in GitHub Desktop.
Quick sort in java
import java.util.Arrays;
public class problemSolving {
static void quickSort(int[] array, int l, int r) {
//We first check if the left-most element index is greater than right-most element index
//This is considered as a base case to exit from infinite recursive calls
if (l >= r) {
return;
}
//We then take the pivot element which may be a random one but we choose the first element for instance
var pivot = partition(array, l, r);
//We make two quick sort for left and hand side arrays recursively.
quickSort(array, l, pivot - 1);
quickSort(array, pivot + 1, r);
}
static int partition(int[] array, int l, int r) {
//We make the first element of the array or sub-array be the pivot
var pivot = array[l];
//We make a counter which helps us to swap between smaller number and bigger number so smaller numbers
//go to the left of pivot and bigger ones go to the right
var j = l;
for (int i = l + 1; i <= r; i++) {
//If the element is smaller than the pivot, move the cursor 'j' to next element and make a swap.
if (array[i] <= pivot) {
j++;
swap(array, j, i);
}
}
//After you push the smaller elements to the right, then you make a swap to the 'j' element and the pivot
swap(array, j, l);
return j;
}
static void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
public static void main(String[] args) {
int[] array = {6, 4, 2, 1, 4, 6, 7, 8, 30, 4, 3, 2};
quickSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment