Ein zentrales Problem in der Informatik besteht im Sortieren von Daten. Das setzt voraus, dass zwischen den Einzeldaten eine Größer-Kleiner-Beziehung existiert, was z.B. bei Zahlen selbst-verständlich ist. Aber auch Zeichen- und Zeichenketten erlauben eine solche Beziehung, die durch das Alphabet gegeben ist. Diese lexikalische Anordnung ist in den meisten Programmier-sprachen implementiert, so dass z.B. in JAVA ein Vergleich der beiden Strings „papst“ > „papier“ möglich ist.

Wir betrachten als Beispiele einfache Felder von Ganzzahlen. Die Überlegungen sind ohne Probleme auf andere sortierbare Datentypen übertragbar.

1. Sortieren durch direktes Auswählen (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:

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.

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.

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.

 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() ;
  }

1. Nummerierter ListenpunktTeste das oben angegebene Java-Programm!
2. 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?
3. Betrachte Minsort und überlege Dir, wie viele Vergleiche zum Sortieren eines Feldes mit n Elementen maximal durchgeführt werden müssen!
4. 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.