Skip to content

Instantly share code, notes, and snippets.

@grvcoelho
Created November 8, 2014 01:15
Show Gist options
  • Save grvcoelho/73970dbdccee0a50d9aa to your computer and use it in GitHub Desktop.
Save grvcoelho/73970dbdccee0a50d9aa to your computer and use it in GitHub Desktop.
Java quicksort algorythm implementation
public class QuickSort {
private static long ifs = 0;;
/**
* @param args
*/
public static long Sort(double[] a, boolean desc) {
ifs = 0;
quicksort(a, 0, a.length-1, desc);
// QuickSort.toString(a);
return ifs;
}
public static void quicksort(double[] a, int p, int r, boolean desc) {
if (p < r) {
int q = partition(a, p, r, desc);
quicksort(a, p, q, desc);
quicksort(a, q + 1, r, desc);
}
}
private static int partition(double[] a, int p, int r, boolean desc) {
if(desc) {
double x = a[p];
int i = p - 1;
int j = r + 1;
while (true) {
i++;
while (i < r && a[i] < x) {
i++;
}
j--;
while (j > p && a[j] > x) {
j--;
}
ifs++;
if (i < j)
swap(a, i, j);
else
return j;
}
} else {
double x = a[p];
int i = p - 1;
int j = r + 1;
System.out.println();
while (true) {
i++;
while (i < r && a[i] > x) {
i++;
}
j--;
while (j > p && a[j] < x) {
j--;
}
ifs++;
if (i < j)
swap(a, i, j);
else
return j;
}
}
}
private static void swap(double[] a, int i, int j) {
// ifs++;
// TODO Auto-generated method stub
double temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void toString(double[] a) {
StringBuilder sb = new StringBuilder("[");
for(int i = 0; i < a.length; i++) {
sb.append(a[i] + ", ");
}
sb.append("]");
System.out.println(sb);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment