Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.concurrent.ThreadLocalRandom;
import java.util.Arrays;
/**
* Quicksort implementation that counts that
* number of comparisons required to perform the sort.
*
* @author Jabari Dash
*/
public class QuickSort {
//------------------------------------------------------------------------------
/**
* Display an array on a new line.
*
* @param a Array to display.
*/
private static void display(int[] a) {
System.out.println(Arrays.toString(a));
}
//------------------------------------------------------------------------------
/**
* Swaps two values in an
* array by index.
*
* @param a Array.
* @param i First index.
* @param j Second index.
*
*/
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
//------------------------------------------------------------------------------
/**
* Shuffles an array.
*
* @param a Array to shuffle.
*/
private static void shuffle(int[] a) {
int j;
for (int i = a.length - 1; i >= 0; i--) {
j = ThreadLocalRandom.current()
.nextInt(0, i + 1);
swap(a, i, j);
}
}
//------------------------------------------------------------------------------
/**
* Sorts an array using quicksort.
*
* @param a Array to sort.
*
* @return Number of data comparisons.
*/
private static int quicksort(int[] a) {
return quicksort(a, 0, a.length - 1);
}
//------------------------------------------------------------------------------
/**
* Sorts a sub-array using quicksort.
*
* @param a Array to sort.
* @param lo Left bound.
* @param hi Right bound.
*
* @return Number of data comparisons.
*/
private static int quicksort(int[] a, int lo, int hi) {
var c = 0;
if (lo >= hi)
return c;
var i = lo;
var j = hi;
var r = ThreadLocalRandom.current().nextInt(lo, hi + 1);
var pivot = a[r];
while (i <= j) {
while (a[i] < pivot) {
i++;
c++;
}
while (a[j] > pivot) {
j--;
c++;
}
if (i <= j) {
swap(a, i, j);
i++;
j--;
}
}
if (lo < j)
c += quicksort(a, lo, j);
if (i < hi)
c += quicksort(a, i, hi);
return c;
}
//------------------------------------------------------------------------------
/**
* Initializes an array such that
* every value is equal to it's index.
*
* @param a Array to initialize.
*/
private static void init(int[] a) {
for (int i = 0; i < a.length; i++)
a[i] = i;
}
//------------------------------------------------------------------------------
public static void main(String[] args) {
int c;
int min = 50;
int max = 5000;
int increment = 50;
int[] a;
System.out.println("n\tE(n)\tE(n)/n^2\tE(n)/n*log(n)");
for (int i = min; i <= max; i += increment) {
a = new int[i];
init(a);
shuffle(a);
c = quicksort(a);
System.out.format("%d\t%d\t%f\t%f\n",
i,
c,
c / Math.pow(i, 2),
c / i * (Math.log(i) / Math.log(2))
);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.