Algorithmen

„Einen Plan zum Lösen eines Problems mit Hilfe einer endlichen Folge eindeutiger und ausführbarer Schritte nennen wir Algorithmus.“

Eine Methode um Werte in einem Array zu tauschen geht:

    private void tauschen(int a,int b)
    {
        int temp = zahl[a];
        zahl[a] = zahl[b];
        zahl[b] = temp;
    }

Das Tauschen von Werten wird beim Sortieren benötigt: Hier werden alle Werte getauscht bis diese in der gewünschten Reihenfolge vorliegen.

    public void sortieren()  
    {
        for(int a=0;a<100;a++)
        {         
            for(int i=0;i<100;i++)
            {
                if(zahl[i]>zahl[a])
                {
                    tauschen(a,i);
                }
            }
        }
    }

Beim BubbleSort-Algorithmus werden immer zwei benachbarte Elemente miteinander verglichen. Ist das eine größer als das andere, werden die beiden Werte vertauscht. Ein kleines Beispiel dazu.

Ausgangslage:

19 5 32 8

Erster Durchlauf

19 5 32 8 » 5 19 32 8
5 19 32 8 » 5 19 32 8
5 19 32 8 » 5 19 8 32

Zweiter Durchlauf

5 19 8 32 » 5 19 8 32
5 19 8 32 » 5 8 19 32
5 8 19 32 » 5 8 19 32

Bei jedem Durchlauf wird auch jedes einzelne Arrayelement mit dem nächsten verglichen. Pro Arrayelement läuft eine äußere und einer innere Schleife durch. In diesem Fall gäbe es hier vier äußere Schleifendurchläufe - in diesem Beispiel ist das Array nach zwei Durchläufen allerdings bereits korrekt sortiert. Man könnte mit entsprechenden Prüfungen nun das Sortieren abbrechen, für die „Grundversion“ ist das aber erstmals unnötig.

public void bubbleSort(int *Array, int Obergrenze)
{
	int x, y;
	int temp;
 	for(x=0;x<=Obergrenze;x++)
	{
		for(y=0;y<=Obergrenze;y++)
		{
			if(y < Obergrenze)
			{
				if(Array[y] > Array[y+1])
				{
					temp = Array[y];
					Array[y] = Array[y+1];
					Array[y+1] = temp;
				}
			}
		}
	}
}

Es kommt in einem Programm ständig vor, dass Werte sortiert werden müssen. Das können Zahlwerte sein oder Zeichenketten. Entscheidend bei Sortiertalgorithmen ist vor allem deren Geschwindigkeit. Einer der einfachsten Sortieralgorithmen ist der „Selection Sort“.

Das Programm sucht erst nach dem kleinsten Element des Feldes, tauscht es gegen das erste Element aus, findet das zweitkleinste Element, tauscht es gegen das zweite Element aus und so weiter, bis das gesamte Feld sortiert ist. Das Programm besteht aus einem Schleifennest. Darunter versteht man mindestens zwei ineinander verschachtelte Schleifen.

In der innersten Schleife findet über eine If-Anweisung der Vergleich zwischen den Elementen statt. Ist ein Minimum gefunden, speichert das Programm es in einer temporären Veriablen und vertauscht es. Danach finden weitere Durchläufe statt, bis das gesamte Feld sortiert ist.

  /**
   * Selection Sort mit Hilfe von 
   * "Einstieg in Java6 - Bernhard Steppan"
   * 
   * @TP, MW
   * @24.01.08
   */
   public class Selection
  {
	  public static void main(String[] sortiere)  {
		  int zahl[]=new int[10];
		  int i, a;
		  zahl[0]=25; zahl[1]=42;
		  zahl[2]=34; zahl[3]=17;
		  zahl[4]=21; zahl[5]=15;
		  zahl[6]=33; zahl[7]=2;
		  zahl[8]=1; zahl[9]=5;
 
		  for (a = 0; a < 9; a++) {
			  for (int b=a; b <9; b++) {
				  if (zahl[a] > zahl[b]) {
					  i = zahl[a];
					  zahl[a] = zahl[b];
					  zahl[b] = i;
				  }
			  }
		  } 
 
		  for (a=0; a<9;a++)
			  System.out.println(zahl[a]);
	  }
  }

Das Sieb des Eratosthenes ist ein Algorithmus zur Bestimmung einer Liste oder Tabelle aller Primzahlen kleiner oder gleich einer vorgegebenen Zahl.

Zunächst werden alle Zahlen 2, 3, 4,… bis zu einer gewünschten Zahl aufgeschrieben.Dann sucht man die kleinste Primzahl. Nachdem eine Primzahl gefunden wurde, werden alle Vielfachen dieser Primzahl aus der Liste oder Tabelle gestrichen. Danach genügt es mit dem Quadrat der Primzahl zu fortzufahren, da alle kleineren Vielfachen bereits gestrichen worden sind. Sobald das Quadrat der Primzahl größer als die gewünschte Höchstzahl ist, sind alle Primzahlen kleiner oder gleich dieser Zahl bestimmt.

Die Primzahlen zwischen 2 und 120 sollen ermittelt werden: Erst werden alle Vielfachen von 2 gestrichen, dann alle Vielfachen von 3, 5, und 7. Da bereits 11^2 = 121 nicht mehr im Wertebereich liegt, werden ab 11 keine zusammengesetzten Zahlen mehr als mögliche Primzahlen gelten. Alle übrigen Zahlen sind Primzahlen.

/**
 *  @author JL, AB
 *  @date   05.06.09
 */
public class Sieb {
 
	/**
	 * Berechnet die Primzahlen von 0 bis max,
	 * in Benutzung des Siebes des Eratosthenes.
	 * 
	 * @param max
	 * @return
	 */
	public static int[] calcPrim(int max) {
		int[] values = new int[max];
		for (int i = 0; i < values.length; i++) {
			values[i] = i;
		}
		// Sucht alle Primzahlen bis zur wurzel(max)
		int[] beginPrims = searchPrims((int) Math.sqrt(max));
		// Setzt alle Mehrfachen der Primzahlen auf 0
		for (int p : beginPrims) {
			for (int j = p + p; j <= max - p; j += p) {
				values[j] = 0;
			}
		}
		return values;
	}
 
	/**
	 * Sucht die Primzahlen von 0 bis max iterativ heraus.
	 * 
	 * @param max Obergrenze
	 * @return int[] mit den gefundenen Primzahlen
	 */
	private static int[] searchPrims(int max) {
		int[] prims = null;
		int cnt = 0;
		for (int i = 2; i <= max; i++) {
			if (isPrim(i)) {
				cnt++;
			}
		}
		prims = new int[cnt];
		cnt = 0;
		for (int i = 2; i < max; i++) {
			if (isPrim(i)) {
				prims[cnt] = i;
				cnt++;
			}
		}
		return prims;
	}
 
	/**
	 * Prüft, ob eine Zahl eine Primzahl ist.
	 * 
	 * @param number zu prüfende Zahl
	 * @return ob Primzahl oder nicht
	 */
	private static boolean isPrim(int number) {
		boolean isPrim = true;
		for (int j = 2; j < number; j++) {
			if (number % j == 0) {
				isPrim = false;
			}
		}
		return isPrim;
	}
	/**
	 * Gibt ein int Array auf die Konsole aus.
	 * 
	 * @param array auszugebenes Array
	 */
	private static void print(int[] array) {
		for (int v : array) {
			System.out.println(v);
		}
	}
 
	public static void main(String[] args) {
		print(calcPrim(100));
	}
}

/**
 * @author JL
 */
public class SiebEx {
 
	private int[] zahlen;
 
	public void arrayFill(int x1, int x2)
        // Füllt den Array
		int x = x2 - x1;
		zahlen = new int[x];
		for (int i = x1; i < x2; i++) {
			zahlen[i - x1] = i;
		}
	}
 
	public void primSuch() {
        // Sucht die Primzahlen zwischen x1 und x2 
		for (int i = 0; i < zahlen.length; i++) {
			for (int j = 2; j < zahlen[i]; j++) {
				if (zahlen[i] % (j) == 0) {
					zahlen[i] = 0;
 
				}
			}
		}
	}
 
	public void ganzenarrayausgibt()
        // unwichtig 
	{
		for (int i = 0; i<zahlen.length; i++)
		{
			System.out.println(zahlen[i]);
		}
	}
 
	public void ausgeben() {
        // Gibt Primzahlen aus
		for (int i = 0; i < zahlen.length; i++) {
			if (zahlen[i] == 0) {
			} else {
				System.out.println(zahlen[i]);
			}
		}
 
	}
 
	public static void main(String[] args) {
		SiebEx ichBinEineVariable = new SiebEx();
		ichBinEineVariable.arrayFill(5, 23042);	
		ichBinEineVariable.primSuch();
		ichBinEineVariable.ausgeben();
	}
 
}

Klasse des Euklidschen Algorithmus (ohne Erklärung):

 /**
 * Der Euklidsche Algorithmus
 * gibt den groessten gemeinsamen Teiler zweier Zahlen wieder.
 * 
 * @author (PT) 
 * @version (8.12.2010)
 */
public class EuklidscherAlgorithmus
{
    public EuklidscherAlgorithmus()
    {        
    }
    
    private int groesstergemeinsamerTeiler(int a, int b)
    {
        int c=a;
        int d=b;
        if(a==0)
        {
            return b;
        }
        if(b==0)
        {
            return a;
        }    
        else
        {
            int r;
            while (b>0)
            {
                r=a%b; //r ist gleich der Rest von a durch b
                a=b;
                b=r;
            }
            return a;
        }    
    }
    
    public void teilerZeigen(int a, int b)
    {
        int c;
        c=groesstergemeinsamerTeiler(a, b);
        System.out.println("Der groesste gemeinsame Teiler ist "+c+".");
    }    
}