MedianOfThree

package aufgabe1InsertionSort;
public class QuickSortMedian extends CountingSorter implements Sorter
{

	private int[] a;
	private int n;

	public void sort(int[] a) {
		this.a = a;
		n = a.length;
		quicksort(0, n - 1);
	}

	private void quicksort(int lo, int hi)
	{
		int i = lo, j = hi;

		// median of three
		int x = median(lo, hi);

		// Aufteilung
		while (i <= j) {
			while (a[c(i)] < x)
				i++;
			while (a[c(j)] > x)
				j--;
			if (i <= j) {
				exchange(i, j);
				i++;
				j--;
			}
		}

		// Rekursion
		if (lo < j)
			quicksort(lo, j);
		if (i < hi)
			quicksort(i, hi);
	}

	// Medianpunkt finden
	private int median( int lo, int hi)
	{
		int center = (lo + hi) / 2;

		if (a[c(lo)] > a[c(center)])
			exchange(lo, center);

		if (a[c(lo)] > a[c(hi)])
			exchange(lo, hi);

		if (a[c(center)] > a[c(hi)])
			exchange(center, hi);

		exchange(center, hi - 1);
		return a[hi - 1];
	}

	private void exchange(int i, int j)
	{
		int t = a[c(i)];
		a[c(i)] = a[c(j)];
		a[c(j)] = t;
	}
} // end class QuickSorter