q1:java-sortierverfahren

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Nächste Überarbeitung		 Vorhergehende Überarbeitung
q1:java-sortierverfahren [2017/07/11 08:37] – angelegt admin03q1:java-sortierverfahren [2017/07/11 08:43] (aktuell) – admin03
Zeile 9: Zeile 9:
  
 Prinzip: Das kleinste Element im unsortierten Teil des Feldes wird mit dem 1. Element des unsortierten Teils getauscht. Danach ist der unsortierte Teil um 1 Element kleiner geworden. Deshalb auch die Bezeichnung „Minsort“. Prinzip: Das kleinste Element im unsortierten Teil des Feldes wird mit dem 1. Element des unsortierten Teils getauscht. Danach ist der unsortierte Teil um 1 Element kleiner geworden. Deshalb auch die Bezeichnung „Minsort“.
 +
 +Beispiel:
 +
 +{{ :q1:unbenannt.png?direct&600 |}}
 +
 +Das Verfahren wird nun auf das unsortierte Restfeld angewendet, bis das Feld schließlich vollständig sortiert ist.
 +
 +Alle Sortierverfahren kann man sich hervorragend mit dem Programm "sortiere.com" klarmachen.
 +
 +2. Sortieren durch direktes Austauschen (BUBBLESORT)
 +
 +Diesem Sortierverfahren liegt das Bild der aufsteigenden Luftblasen zugrunde. Es sortiert in der Weise, dass die Zahlen, beginnend mit der kleinsten, der Reihe nach nach "oben" (vorne) steigen.
 +Prinzip: Je zwei benachbarte Elemente des unsortierten  Teils werden miteinander verglichen und bei "falscher" Ordnung getauscht.
 +
 +{{ :q1:sortiere2.png?direct&600 |}}
 +
 +**Verbesserung:** Eventuell ist das Feld schon einige Durchläufe vor dem Ende fertig sortiert. Dies kann man abfragen, indem mit einer boolschen Variablen überprüft, ob überhaupt noch Tauschaktionen stattgefunden haben.
 +
 +Um die Sortierverfahren in Java zu implementieren, benötigt man einen geeigneten Datentyp.
 +Der soll im nächsten Kapitel erläutert werden.
 +
 +====== Realisierung der beiden Sortierverfahren ======
 +
 +
 +Bubblesort und Minsort sollen nun als Java-Programme realisiert werden. Dabei wird ein Feld Sortfeld geschaffen und eine globale Variable aktugroesse, in die der Benutzer eine tatsächliche Größe eingibt, d.h. auch wenn 50000 Feldelemente reserviert wurden, kann der Anwender z.B. nur die ersten 10 davon für sein Feld nutzen. Die Feldelemente sollen long-Zahlen im Bereich zwischen 0 und 1 Million sein.
 +
 +bubblesort und minsort sollen Methoden im Programm sein. Weitere Methoden sind fuellezufaellig, die das Feld bis zur aktugroesse mit zufallszahlen füllt und gibaus, die das sortierte Feld in ein jTextArea ausgibt. In einem weiteren jTextField wird die Zeit gestoppt, die die Methode zum Sortieren braucht. Betrachten Sie diesen Teil als black-box, die noch nicht verwendete Java-Konstrukte verwendet.
 +
 +<code JAVA>
 + public static final int FELDGROESSE =  1000000 ;
 +  private long[] werte = new long[FELDGROESSE] ;
 +  private int aktuGroesse ;
 +  private int zahlenGroesse ;
 +  public void fuelleZufaellig ()
 +  {
 +   for (int i=0; i<= aktuGroesse-1;i++)
 +      werte[i] = (long)(Math.random()*zahlenGroesse) ;
 +  }
 +  public void gibAus()
 +  {
 +   for (int i=0; i<= aktuGroesse-1 ;i++)
 +      jTextArea1.append(String.valueOf(werte[i]) + "-") ;
 +  }
 +  public void tausche(int i, int j)
 +  {
 +      long temp = werte[i] ;
 +      werte[i] = werte[j] ;
 +      werte[j] = temp ;
 +  }
 +  public void bubblesort()
 +  {
 +   for (int durchlauf = 1 ; durchlauf < aktuGroesse ; durchlauf++)
 +      {
 +       int sortiertBeginn = aktuGroesse ;
 +       for (int pos = 0 ; pos < sortiertBeginn-1 ; pos++)
 +          {
 +           if (werte[pos] > werte[pos+1])
 +             tausche(pos,pos+1) ;
 +          }
 +            sortiertBeginn-- ;
 +      }
 +  }
 +  public void minsort()
 +  {
 +   int unsortiertBeginn = 0 ;
 +   for (int durchlauf = 1 ; durchlauf < aktuGroesse ; durchlauf++)
 +      {
 +       int minpos = unsortiertBeginn ;
 +       long minimum = werte[unsortiertBeginn] ;
 +       for (int pos = unsortiertBeginn ; pos < aktuGroesse ; pos++)
 +          {
 +           if (werte[pos] < minimum)
 +             {
 +              minpos = pos ;
 +              minimum = werte[pos] ;
 +             }
 +          }
 +       tausche(unsortiertBeginn,minpos) ;
 +       unsortiertBeginn++ ;
 +      }
 +  }
 +
 +public void jButton1_ActionPerformed(ActionEvent evt)
 +  {
 +    jTextArea1.setText("") ;
 +    jTextArea1.setLineWrap(true) ;
 +    aktuGroesse = Integer.parseInt(jTextField1.getText()) ;
 +    zahlenGroesse = Integer.parseInt(jTextField3.getText()) ;
 +    fuelleZufaellig() ;
 +    if (jRadioButton1.isSelected())
 +      {
 +       gibAus() ;
 +       jTextArea1.append("\n") ;
 +      }
 +    jButton2.setVisible(true) ;
 +    jButton3.setVisible(true) ;
 +    jButton4.setVisible(true) ;
 +  }
 +
 +  public void jButton2_ActionPerformed(ActionEvent evt)
 +  {
 +    long startTime = System.currentTimeMillis();
 +    minsort() ;
 +    long timeNow = System.currentTimeMillis();
 +    double diff = (timeNow-startTime)/1000.0 ;
 +    jTextField2.setText(Double.toString(diff)) ;
 +    if (jRadioButton1.isSelected())
 +       gibAus() ;
 +  }
 +
 +  public void jButton3_ActionPerformed(ActionEvent evt)
 +  {
 +
 +    long startTime = System.currentTimeMillis();
 +    bubblesort() ;
 +    long timeNow = System.currentTimeMillis();
 +    double diff = (timeNow-startTime)/1000.0 ;
 +    jTextField2.setText(Double.toString(diff)) ;
 +    if (jRadioButton1.isSelected())
 +       gibAus() ;
 +  }
 +</code>
 +====== Aufgaben ======
 +
 +  - Nummerierter ListenpunktTeste das oben angegebene Java-Programm!
 +  - Wähle zufällig ein unsortiertes Feld mit 5 Elementen und führe die beiden Methoden bubblesort() und minsort() konkret und schrittweise durch. Notiere für alle vorkommenden Variablen ihre Werte im Laufe der Zeit und ergänze den Quelltext durch sinnvolle Kommentare! Welche Aufgaben haben die Variablen sortiertBeginn und unsortiertBeginn?
 +  - Betrachte Minsort und überlege Dir, wie viele Vergleiche zum Sortieren eines Feldes mit n Elementen maximal durchgeführt werden müssen!
 +  - Informiere Dich über das Verfahren InsertSort und baue es in das Sortierprogramm ein
 +
 +
 +**Ergänzung zu Aufgabe 3:**
 +
 +Die einfachen Sortierverfahren Bubblesort und Minsort besitzen zwei geschachtelte Schleifen. Die äußere wird ca. n mal durchlaufen (genauer gesagt n-1). Dabei ist n die Anzahl der zu sortierenden Elemente. Die innere Schleife wird zwischen 1 mal und n mal durchlaufen, je nachdem, wie viel Elemente sich schon im sortierten Teil befinden. Im Mittel wird die innere Schleife also   mal ausgeführt. Die Zeit für die jeweiligen Operationen kann man schwerer schätzen, da man nicht genau weiß, wie das Verhältnis Vergleiche-Vertauschungen ist.
 +
 +Es gilt aber ziemlich genau folgendes: Die Anzahl der Operationen wächst mit , also quadratisch. Benötigt ein Programm 25 Sekunden für 10.000 Elemente, dann wird es für 20.000 Elemente schon   Sekunden = 100 Sekunden benötigen. Praktische Tests zeigen, dass Bubble-Sort dabei etwa doppelt solange braucht wie Min-Sort.
 +
 +In der Praxis werden für große zu sortierende Felder schnellere Verfahren eingesetzt, deren Laufzeit langsamer als quadratisch mit n wächst. Das schnellste bekannte Verfahren ist das vom Engländer Charles Antony Richard Hoare 1962 erfundene Quicksort, mit dem wir uns im nächsten Kapitel beschäftigen werden.
 +
  
  • /var/www/infowiki/data/attic/q1/java-sortierverfahren.1499762273.txt.gz
  • Zuletzt geändert: 2017/07/11 08:37
  • von admin03