Skip to content

Instantly share code, notes, and snippets.

@hrishikesh-mishra

hrishikesh-mishra/QuickSortWithHoarePartition.java

Created April 15, 2017 15:43
Show Gist options
  • Save hrishikesh-mishra/dde8106d3bf926d1d2defedff999c907 to your computer and use it in GitHub Desktop.
Save hrishikesh-mishra/dde8106d3bf926d1d2defedff999c907 to your computer and use it in GitHub Desktop.
Download ZIP
Quick Sort With Hoare Partition
Raw
QuickSortWithHoarePartition.java
package com.hrishikesh.practices.sort;
import java.util.Arrays;
/**
* Problem:
* Quick Sort With Hoare Partition
*
* @author hrishikesh.mishra
*/
public class QuickSortWithHoarePartition {
public static void sort(int[] array) {
sortHelper(array, 0, array.length - 1);
}
private static void sortHelper(int[] array, int p, int r) {
if (p < r) {
int q = doHoarePartitioning(array, p, r);
sortHelper(array, p, q);
sortHelper(array, q + 1, r);
}
}
private static int doHoarePartitioning(int[] array, int p, int r) {
int pivot = array[p];
int i = p - 1;
int j = r + 1;
while (true) {
do {
i++;
}
while (array[i] < pivot);
do {
j--;
}
while (array[j] > pivot);
if (i < j) {
swap(array, i, j);
} else {
return j;
}
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
class QuickSortWithHoarePartitionTest {
public static void main(String[] args) {
int[] array = {2, 8, 7, 1, 3, 5, 6, 4};
System.out.println("Before Array: " + Arrays.toString(array));
QuickSortWithHoarePartition.sort(array);
System.out.println("After Array: " + Arrays.toString(array));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment