class QuicksortDemo
{ final int MAXINDEX = 99999;
  int[] feld;
  Stoppuhr t;
   
  public QuicksortDemo()
  { feld = new int[MAXINDEX+1];
    t = new Stoppuhr();
  }

  void feldFuellen()
  { for (int i=0; i<=MAXINDEX; i++)
    {  feld[i] = (int)Math.round(Math.random()*9000.0 + 100); }
  } // feldFuellen

  void feldAusgabe()
  { System.out.println("Das Feld enthaelt die folgenden Elemente: ");
    for (int i=0; i<=MAXINDEX; i++)
         System.out.print(feld[i] + " ");
    System.out.println();
  } // feldAusgabe

  void vertausche (int a, int b)
  {  int ablage = feld[a];
     feld[a] = feld[b];
     feld[b] = ablage;
  } // vertausche

  void quicksort(int links, int rechts)
  { int nachlinks = rechts; // Laufindex, der vom rechten Ende nach links laeuft
    int nachrechts = links; // Laufindex, der vom linken Ende nach rechts laeuft
    if (nachrechts < nachlinks)
       { // Pivotelement bestimmen
         // int pivot = feld[(nachrechts + nachlinks)/2];
         int pivot = feld[links];

         while (nachrechts <= nachlinks)
         {    // Links erstes Element suchen, das
              // groesser oder gleich dem Pivotelement ist
              while ((nachrechts < rechts) && (feld[nachrechts] < pivot))
                   nachrechts++;

              // Rechts erstes Element suchen, das
              // kleiner oder gleich dem Pivotelement ist
              while ((nachlinks > links) && (feld[nachlinks] > pivot))
                   nachlinks--;

              // Wenn nicht aneinander vorbei gelaufen, Inhalte vertauschen
              if (nachrechts <= nachlinks)
                   { vertausche(nachrechts, nachlinks);
                     nachrechts++;
                     nachlinks--;
                   }
         } // end while

         // Linken Teil sortieren
         if (nachlinks > links) quicksort (links, nachlinks);

         // Rechten Teil sortieren
         if (nachrechts < rechts) quicksort (nachrechts, rechts);

       } // end if
  }  // quicksort

  boolean richtigSortiert()
  {  for (int i=0; i<MAXINDEX; i++)
           if (feld[i]>feld[i+1]) return false;
     return true;
  }

  public void action()
  { System.out.println("Quicksort-Demo: ");
    feldFuellen();
//    feldAusgabe();
    t.starte();
    quicksort(0, MAXINDEX);
    t.stoppe();
//    feldAusgabe();
    System.out.println("Zeit: " + t.lies() + " ms.");
        if (richtigSortiert()) System.out.print("Sortierung OK!");
        else System.out.print("Sortierung FALSCH!");
  } // main
} // class quicksort