Untitled

package de.hawhamburg.hamann.ad.sortingworkbench.sorter;

import java.util.List;
import java.util.Random;

import de.hawhamburg.hamann.ad.sortingworkbench.SortingMetrics;

public class QuickSort implements Sorter {

	@Override
	public String getName() {
		return "QuickSort";
	}

	@Override
	public <T extends Comparable<T>> void sort(List<T> toSort, SortingMetrics metrics) {
	
		if(toSort.size() > 0)
		{
			quicksort(toSort, 0, toSort.size() - 1, metrics);
		}
			for (int i = 0; i < toSort.size(); i++) {
				System.out.print(toSort.get(i)+ ",");
			}
			System.out.print("!");
	}

	private <T extends Comparable<T>> void quicksort(List<T> toSort, final int erstes, final int letztes, SortingMetrics metrics) {

		/*
		 * Aufteilung des Arrays in die zwei Teilfolgen. Linke Seite kleiner als Pivot -
		 * rechte Seite größer als Pivot
		 */
		int index = teilung(toSort, erstes, letztes, metrics);

		/*
		 * repräsentiert die linke Seite des Pivot-Element.
		 */
		if (erstes < index - 1) {
			quicksort(toSort, erstes, index - 1, metrics);
		}

		/*
		 * repräsentiert die rechte Seite des Pivot-Element.
		 */
		if (index < letztes) {
			quicksort(toSort, index, letztes, metrics);
		}

	}

	private <T extends Comparable<T>> int teilung(List<T> toSort, final int erstes, final int letztes, SortingMetrics metrics) {
		
//		int pivot = erstes;
//		int pivot = erstes + (letztes-erstes)/2;
		int pivot= (toSort.indexOf(toSort.get(erstes))+ toSort.indexOf(toSort.get(letztes)))/2;
//		int pivot = (erstes+letztes)/2;
//		int pivotThree = (toSort.indexOf(toSort.get(erstes))+ toSort.indexOf(toSort.get(letztes))+(toSort.indexOf(toSort.get(erstes))+ toSort.indexOf(toSort.get(letztes)))/2)/3;
//		Random rand = new Random();
//		int pivot =  rand.nextInt(((letztes-1)-erstes)+1)+erstes;
//		int pivot = 0;
//		
//		if(toSort.get(erstes).compareTo(toSort.get(letztes))<= 0 && toSort.get(erstes).compareTo(toSort.get(pivotMitte))<= 0)
//		{
//			pivot = erstes;
//			
//		}
//		else if (toSort.get(letztes).compareTo(toSort.get(pivotMitte))<= 0 && toSort.get(letztes).compareTo(toSort.get(erstes))<= 0)
//		{
//			pivot = letztes;
//			metrics.incrementCompares();
//			metrics.incrementCompares();
//		}
//		else
//		{
//			pivot = pivotMitte;
//		}
//		
		/*
		 * Zeigt auf das erste Element der Liste.
		 */
		int positionLinks = erstes;

		/*
		 * Zeigt auf das letzte Element der Liste.
		 */
		int positionRechts = letztes;

		while (positionLinks <= positionRechts) {
			metrics.incrementCompares();
			/*
			 * Solange die Elemente auf der linken Seite kleiner als das Pivot-Element sind,
			 * erhöhe die Position.
			 */
			while (toSort.get(positionLinks).compareTo(toSort.get(pivot)) < 0) {
				metrics.incrementCompares();
				positionLinks++;
			}

			metrics.incrementCompares();
			/*
			 * Solange die Elemente auf der rechten Seite größer als das Pivot-Element sind,
			 * verringere die Position.
			 */ 
			while (toSort.get(positionRechts).compareTo(toSort.get(pivot)) > 0){
				metrics.incrementCompares();
				positionRechts--;
			}

			if (positionLinks <= positionRechts) {
				swap(toSort, positionRechts, positionLinks, metrics);
				positionLinks++;
				positionRechts--;


			}
		}

		return positionLinks;
	}

}