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]);
                 while ((untergrenze < obergrenze) && //Debug-Punkt 2
                        (qc.kleinerAls(elemente[untergrenze],
                                    elemente[vergleichemit]) <= 0)) {
                     ++untergrenze;
                 } //zähle untergrenze herauf solange die elemente kleiner sind
                 while ((obergrenze >= untergrenze) && //Debug-Punkt 3
                        (qc.kleinerAls(elemente[obergrenze],
                                    elemente[vergleichemit]) > 0)) {
                	//Wäzle obergrenze herunter solange die elemente grösser sind
                     --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];  //vergausche 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){
    	 Quicksort s=new Quicksort();
    	 String[] sort={"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","1960","von","C.","Antony","R.","Hoare","in","seiner","Grundform","entwickelt","und","seitdem","von","vielen","Forschern","verbessert."};
    	 s.quicksort(sort, 0, sort.length-1, new StringVergleich());
    	 for(int i=0;i<sort.length;i++){
    		 System.out.println(sort[i]);
    	 }
    	 
    	 
     }
 }