Workshop - Algorithmen

1 Sortieralgorithmen

Die folgenden Sortieralgorithmen sortieren eindimensionale Arrays

1.1 BubbleSort

Beim BubbleSort werden zwei nebeneinander stehende Werte miteinander verglichen und ein Tausch durchgeführt, wenn eine Bedingung erfüllt ist.

Im folgenden Beispiel wird ein kleines 1D-Array mit Zahlen sortiert.

public void bubbleSort()
{
   int[] zahlen = {4,5,7,0,2,3,1,9,8};
   for (int rechterIndex = zahlen.length - 1;rechterIndex > 0; rechterIndex--)
   {
      for (int linkerIndex = 0; linkerIndex < rechterIndex; linkerIndex++)
      {
         if (zahlen[linkerIndex] > zahlen[linkerIndex + 1])
         {
            int tausch = zahlen[linkerIndex];
            zahlen[linkerIndex] = zahlen[linkerIndex + 1];
            zahlen[linkerIndex + 1] = tausch;
         }
      }
   }
}

1.2 Methode des kleinsten Elements

Dieser Algorithmus durchläuft das 1D-Array von links nach rechts und vergleicht den linken Wert mit allen nebenliegenden rechten Werten.

Ist der linke Wert größer als der rechte, erfolgt ein Tausch untereinander.

public void methodeDesKleinstenElements()
{
   int[] zahlen = {4,5,7,0,2,3,1,9,8};
   for (int linkerIndex = 0; linkerIndex < zahlen.length-1; linkerIndex++)
   {
      for(int rechterIndex = linkerIndex + 1; rechterIndex < zahlen.length; rechterIndex++)
      {
         if(zahlen[linkerIndex] > zahlen[rechterIndex])
         {
            int tausch = zahlen[linkerIndex];
            zahlen[linkerIndex] = zahlen[rechterIndex];
            zahlen[rechterIndex] = tausch;
         }
      }
   }
}

2 Suchalgorithmen

2.1 Sequentielle Suche

Funktioniert bei sortierten und unsortierten Arrays.

Das Array wird von vorn bis hinten durchlaufen und jedes Element mit dem Suchwert verglichen.

Wenn es gefunden oder nicht gefunden wurde, erfolgt eine entsprechende Ausgabe.

public void sequentielleSuche()
{
   int[] zahlen = {0,1,2,3,4,5,6,7,8,9};
   int suchwert = 3;
   
   boolean gefunden = false;
   int position = 0;
   
   while (position < zahlen.length - 1  && !gefunden)
   {
      if (zahlen[position] == suchwert)
      {
         gefunden = true;
      }
      position++;
   }
   
   if (gefunden)
   {
      System.out.println("Gefunden an Position: " + position);
   }
   else
   {
      System.out.println("Nicht gefunden");
   }
}

2.2 Binäre Suche (nur sortierte Arrays)

Funktioniert nur bei sortierten Arrays.

Dabei geht der Algorithmus wie folgt vor:

public void binaereSuche()
{
   int[] zahlen = {0,1,2,3,4,5,6,7,8,9};
   int suchwert = 3;
   
   int linkerIndex = 0;
   int rechterIndex = zahlen.length - 1;
   int mitte;
   
   while (true)
   {
      mitte = (linkerIndex + rechterIndex) / 2;
      if (zahlen[mitte] == suchwert) break;
      
      if (zahlen[mitte] < suchwert)
      {
         linkerIndex = mitte + 1;
      }
      else
      {
         rechterIndex = mitte - 1;
      }
      
      if (linkerIndex > rechterIndex) break;
   }
   if (linkerIndex <= rechterIndex)
   {
      System.out.println("Gefunden an Position: " + mitte);
   }
   else
   {
      System.out.println("Nicht gefunden");
   }
}

Binäre Suche auf Lego Art ;o)

  1. hier bietet sich eine Endlosschleife mit verschiedenen Abbruch-Bedingungen an
  2. erst wird die Mitte bestimmt durch Addition des linken und des rechten Index, welcher durch 2 geteilt wird
  3. nun wird geprüft ob die Mitte bereits den Suchwert enthält, trifft dies zu wird die Schleife verlassen
  4. wenn dies nicht zutrifft wird geprüft ob die Mitte:
    • kleiner als der Suchwert ist, ist dem so, wird linkerIndex auf den Wert von Mitte gesetzt und um eins erhöht
    • oder größer als der Suchwert ist, ist dem so, wird rechterIndex auf den Wert von Mitte gesetzt und um eins vermindert
  5. nun wird noch geprüft ob linkerIndex größer rechterIndex ist und im zutreffenden Fall die Schleife beendet
  6. Dies erfolgt jetzt solange bist der Wert gefunden wurde oder linkerIndex größer rechterIndex ist und damit aussagt, dass der Wert nicht enthalten ist.
  7. Anschließend erfolgte eine Textausgabe

3 Sonstige Algorithmen

3.1 Quersumme berechnen

Wenn man die einzelnen Ziffern einer Zahl miteinander addiert, hat man die Quersumme gebildet.

public void querSumme()
{
   int zahl = 1122;
   int querSumme = 0;
   while (zahl > 0)
   {
      querSumme = querSumme + (zahl % 10);
      zahl = zahl / 10;
   }
   
   System.out.println("Die Quersumme lautet: " + querSumme);
}
  1. erstmal brauchen wir eine Zahl (im Beispiel 1122 (Quersumme = 6))
  2. die quersumme muss in einer entsprechenden Variable gespeichert werden
  3. nun läuft eine Schleife solange wie zahl größer 0 ist
  4. jetzt wird eine Restermittlung von zahl mit 10 durchgeführt, dabei erhalten wir die letzte Stelle der Zahl und addieren sie zu quersumme
  5. danach teilen wir die zahl durch 10 und fangen das Ergebnis in zahl auf, dabei machen wir uns die Integer-Division zunutze, die Nachkommastellen abschneidet
  6. Nach verlassen der Schleife wird das Ergebnis ausgegeben

3.2 Fakultät berechnen

Ein Produkt aus allen natürlichen Zahlen, von eins beginnend, bis zu einer festgelegten Zahl

public void fakultaet()
{
   int ende = 8;
   int fakultaet = 1;
   
   if ( ende >= 0 )
   {
      while ( ende > 1 )
      {
         fakultaet = fakultaet * ende;
         ende = ende - 1;
      }
      System.out.println( "Fakultaet ist " + fakultaet );
   }
   else
   {
      System.out.println("ende muss 0 oder groesser sein");
   }
}