Created
March 28, 2020 17:14
-
-
Save YusufAbdelaziz/4f0d83b07be99f595aea03f19e269f8d to your computer and use it in GitHub Desktop.
Quick sort in java
This file contains hidden or 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
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