Skip to content

Instantly share code, notes, and snippets.

@19h
Created February 7, 2012 23:00
Show Gist options
  • Save 19h/1762730 to your computer and use it in GitHub Desktop.
Save 19h/1762730 to your computer and use it in GitHub Desktop.
IntroHeap
public interface Sorter {
void sort(Sortable[] f, int from, int to);
/**
* Ascendingly sorts the array from from to to,
* where from is included and to is not.
**/
void sort(Sortable[] f);
}
public interface Sortable {
boolean smaller(Sortable ob);
}
private static Sortable[] createMedianOf3KillerArray(int length) {
if ((length % 2) == 1) return null;
int k = length / 2;
Sortable[] a = new Sortable[length];
for (int i = 1; i <= k; i++) {
if ((i\ % 2) == 1) {
a[i - 1] = new SortableInteger(i);
a[i] = new SortableInteger(k + i);
}
a[k + i - 1] = new SortableInteger(2 * i);
}
return a;
}
public class Introsort implements Sorter {
/*
* Class Variables
*/
private static Sortable[] a;
private static int size_threshold = 16;
/*
* Public interface
*/
public void sort(Sortable[] a0) {
a = a0;
introsort_loop(0, a.length, 2 * floor_lg(a.length));
insertionsort(0, a.length);
}
public void sort(Sortable[] a0, int begin, int end) {
if (begin < end) {
a = a0;
introsort_loop(begin, end, 2 * floor_lg(end - begin));
insertionsort(begin, end);
}
}
/*
* Quicksort algorithm modified for Introsort
*/
private static void introsort_loop(int lo, int hi, int depth_limit) {
while (hi - lo > size_threshold) {
if (depth_limit == 0) {
heapsort(lo, hi);
return;
}
depth_limit = depth_limit - 1;
int p = partition(lo, hi, medianof3(lo, lo + ((hi - lo) / 2) + 1, hi - 1));
introsort_loop(p, hi, depth_limit);
hi = p;
}
}
private static int partition(int lo, int hi, Sortable x) {
int i = lo, j = hi;
while (true) {
while (a[i].smaller(x)) i++;
j = j - 1;
while (x.smaller(a[j])) j = j - 1;
if (!(i < j)) return i;
exchange(i, j);
i++;
}
}
private static Sortable medianof3(int lo, int mid, int hi) {
if (a[mid].smaller(a[lo])) {
if (a[hi].smaller(a[mid])) return a[mid];
else {
if (a[hi].smaller(a[lo])) return a[hi];
else return a[lo];
}
} else {
if (a[hi].smaller(a[mid])) {
if (a[hi].smaller(a[lo])) return a[lo];
else return a[hi];
} else return a[mid];
}
}
/*
* Heapsort algorithm
*/
private static void heapsort(int lo, int hi) {
int n = hi - lo;
for (int i = n / 2; i >= 1; i = i - 1) {
downheap(i, n, lo);
}
for (int i = n; i > 1; i = i - 1) {
exchange(lo, lo + i - 1);
downheap(1, i - 1, lo);
}
}
private static void downheap(int i, int n, int lo) {
Sortable d = a[lo + i - 1];
int child;
while (i <= n / 2) {
child = 2 * i;
if (child < n && a[lo + child - 1].smaller(a[lo + child])) {
child++;
}
if (!d.smaller(a[lo + child - 1])) break;
a[lo + i - 1] = a[lo + child - 1];
i = child;
}
a[lo + i - 1] = d;
}
/*
* Insertion sort algorithm
*/
private static void insertionsort(int lo, int hi) {
int i, j;
Sortable t;
for (i = lo; i < hi; i++) {
j = i;
t = a[i];
while (j != lo && t.smaller(a[j - 1])) {
a[j] = a[j - 1];
j--;
}
a[j] = t;
}
}
/*
* Common methods for all algorithms
*/
private static void exchange(int i, int j) {
Sortable t = a[i];
a[i] = a[j];
a[j] = t;
}
private int floor_lg(int a) {
return (int)(Math.floor(Math.log(a) / Math.log(2)));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment