public class Quicksort {

    public interface vergleiche {
        public int kleinerAls(Object a, Object b);
    }

    private static class StringVergleich implements vergleiche {

    	public int kleinerAls(Object a, Object b) {  
            return ((String)a).compareTo((String)b);   
    	}

    }

    public static void quicksort(Object[] elemente,
                                 int start,
                                 int end,
                                 vergleiche qc) {

        if (start < end) { //Debug-Punkt 1
            Object temp;
            int vergleichemit, untergrenze, obergrenze;
            vergleichemit = start;
            untergrenze = start+1;
            obergrenze = end;
            while (true) {
                System.out.println("vergleichemit= "+elemente[vergleichemit]);
                //zaehle untergrenze herauf solange die elemente kleiner sind
                for (; (untergrenze < obergrenze) && // Debug-Punkt 2
						(qc.kleinerAls(elemente[untergrenze],
								elemente[vergleichemit]) <= 0); ++untergrenze);
                //zaehle obergrenze herunter solange die elemente groesser sind
                for (; (obergrenze >= untergrenze) && // Debug-Punkt 3
                (qc.kleinerAls(elemente[obergrenze],
                        elemente[vergleichemit]) > 0); --obergrenze );
                if (untergrenze < obergrenze) { //Debug-Punkt 4 //falls sich die grenzen noch nicht erreicht haben
                    System.out.println("tausche "+ elemente[untergrenze] +"  "+ elemente[obergrenze]);
                    temp = elemente[untergrenze];  //vertausche die elememnte an oberer und unterer grenze
                    elemente[untergrenze] = elemente[obergrenze]; 
                    elemente[obergrenze] = temp;
                } else {
                    break;
                }
            }
            temp = elemente[vergleichemit]; 
            System.out.println("pivotausche "+ elemente[vergleichemit] +"  "+ elemente[obergrenze]);
            elemente[vergleichemit] = elemente[obergrenze]; //mache obergrenze zu pivot
            elemente[obergrenze] = temp; //setze pivot an obergrene

            quicksort(elemente, start, obergrenze, qc);
            quicksort(elemente, obergrenze+1, end, qc);
        }
    }
     
    public static void main(String[] args){
    	 
        String input = "Quicksort (von engl. quick - schnell, to sort - sortieren) ist ein schneller, " +
                       "rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche " +
                       "(lat. Divide et impera!, engl. Divide and conquer) arbeitet. Er wurde ca. 1960 von C. " +
                       "Antony R. Hoare in seiner Grundform entwickelt und seitdem von vielen Forschern verbessert.";

        String[] words = input.split(" ");
    	 
        Quicksort.quicksort(words, 0, words.length-1, new StringVergleich());
        for(int i=0; i < words.length; i++){
            System.out.println(words[i]);
    	}
     }

 }