Skip to content

Instantly share code, notes, and snippets.

@flexelem
Last active August 29, 2015 14:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save flexelem/9bd3b18f867c7182cadc to your computer and use it in GitHub Desktop.
Save flexelem/9bd3b18f867c7182cadc to your computer and use it in GitHub Desktop.
Quicksort algorithm in java
import java.util.Random;
public class RandomizedQuickSort {
public void quickSort(int[] numbers, int low, int high) {
if (low < high) {
// select pivot randomly
int q = randomizedPartition(numbers, low, high);
quickSort(numbers, low, q - 1);
quickSort(numbers, q + 1, high);
}
}
private int randomizedPartition(int[] numbers, int low, int high) {
Random rand = new Random();
int randomPivot = rand.nextInt(high - low + 1) + low;
swap(numbers, randomPivot, high);
return partition(numbers, low, high);
}
private int partition(int[] numbers, int low, int high) {
// select the right most number as pivot
int pivot = numbers[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (numbers[j] <= pivot) {
i++;
swap(numbers, j, i);
}
}
// finally swap the pivot with the first number which is
// greater then pivot
swap(numbers, i + 1, high);
// return the index of pivot
return i + 1;
}
// swap the numbers given from indices of numbers array
private void swap(int[] numbers, int j, int i) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment