fh.h42.de - What´s the question?
Navigation: [START] [00-ws] [prog] [p-java004.htm]
[print]  [e-mail]  [main]

Java - Felder & Bubblesort-Algorithmus


Lösung zu Übung 13, Aufgabe 1:
/*
$DATE (19.01.2001)
$AUTH Lars Ehrhardt
$VER  1.0
 */

import java.util.*;

class bruch {
    public static void main(String arguments[]){
        int[] feld = new int[2];
        Random r = new java.util.Random();
        int a, b, c, d;

        a = r.nextInt() % 100 + 1;
        b = r.nextInt() % 100 + 1;
        c = r.nextInt() % 100 + 1;
        d = r.nextInt() % 100 + 1;

        bruchop(a,b,c,d,'+');
              bruchop(a,b,c,d,'-');
        bruchop(a,b,c,d,'*');
        bruchop(a,b,c,d,':');
    }


    /* Funktion: Bruchop
       Übergabewerte: Zahl 1: a/b, Zahl 2 a/b, op: +,-,:,*
       Rückgabewerte: keine
     */

    public static void bruchop(int a,int b, int c, int d, char op){

        int[] zahla = new int[2];
        zahla = convbruch(a,b,false);

        int[] zahlb = new int[2];
        zahlb = convbruch(c,d,false);

        switch(op) {
        case '+': System.out.print("(" + a + "/" + b + ") + (" + c + "/" + d + ") = "); convbruch((zahla[0]*zahlb[1] + zahla[1]*zahlb[0]), zahla[1]*zahlb[1],true);break;
         case '-':  System.out.print("(" + a + "/" + b + ") - (" + c + "/" + d + ") = "); convbruch((zahla[0]*zahlb[1] - zahla[1]*zahlb[0]), zahla[1]*zahlb[1],true);break;
         case '*':  System.out.print("(" + a + "/" + b + ") * (" + c + "/" + d + ") = "); convbruch (zahla[0]*zahlb[0],zahla[1]*zahlb[1],true);break;
         case ':':  System.out.print("(" + a + "/" + b + ") : (" + c + "/" + d + ") = "); convbruch (zahla[0]*zahlb[1],zahla[1]*zahlb[0],true);break;
         default: System.out.println("Fehler: Nur Operatoren +,-,* und : erlaubt!"); break;
        } //end switch
    } //end bruchop


    /* Funktion:  convbruch
       Uebergabeparameter:
       Rückgabeparameter:

    */

    public static int[] convbruch(int zaehler, int nenner, boolean normieren){
        int[] bruch = new int[2];
        bruch[0] = zaehler;
        bruch[1] = nenner;

        if (bruch[0] != 0 && bruch[1] != 0)  { // Kuerzen durch ggT-Bestimmung!
            int ggtwert;
            ggtwert = ggT(bruch[0],bruch[1]);
            bruch[0] = bruch[0]/ggtwert;
            bruch[1] = bruch[1]/ggtwert;
        }

        if (normieren==true) {
            if (bruch[0] < 0 && bruch[1] < 0 || bruch[1] < 0) { // Vorzeichenbereinigung
                bruch[0] = bruch[0]/(-1);
                bruch[1] = bruch[1]/(-1);
            }

            if (bruch[1] == 0)
                System.out.println("Fehler: 0-Division!");
            else {
                System.out.print(bruch[0]); // Zaehlerausgabe
                if (bruch[0] != 0 && bruch[1] != 1) {  //Ausgabe, falls Zaehler != 0 und Nenner != 1
                    System.out.print("/");
                    System.out.print(bruch[1]);
                }
                System.out.println(""); //Zeilenabschluss
            }
        }
        return(bruch);
    }

    /* Funktion: ggT
       Uebergabeparameter: a (int), b (int)
       Rueckgabeparameter: a (int) (groesste Zahl)
       Die beiden if - Konstrukte sind nötig, da diese Funktion nur den
       ggT von zwei positiven Zahlen berechnet!
    */

    public static int ggT (int a, int b){
        if (a < 0) a = a/-1;
        if (b < 0) b = b/-1;
        while (a != b) {
            if (a > b)
                a = a - b;
            else
                b = b - a;
        } // end while
        return(a);
    } //end ggT
}

Lösung zu Übung 13, Aufgabe 2:

Bubble-Sortalgorithmus

Beim Bubble-Sortalgorithmus werden zwei Zahlen einer Folge jeweils verglichen. Sollte die linke Zahl größer sein als die Rechte, so werden die Zahlen getauscht. Dadurch steht bei der 1. Abarbeitung die größte Zahl der Folge an letzter Stelle. Danach fängt der Algorithmus wieder beim 1. Zeichen an und das Ganze wiederholt sich.

Beispiel:
Eingabefolge: 10, 8, 6, 4, 2, 1, 3, 5, 7, 9

1. Lauf:
10 > 8 wahr: 10, 8 werden getauscht: Resultat: 8 10 6 4 2 1 3 5 7 9
10 > 6 wahr: 10, 6 werden getauscht: Resultat: 8 6 10 4 2 1 3 5 7 9
10 > 4 wahr: 10, 4 werden getauscht: Resultat: 8 6 4 10 2 1 3 5 7 9
10 > 2 wahr: 10, 2 werden getauscht: Resultat: 8 6 4 2 10 1 3 5 7 9
10 > 1 wahr: 10, 1 werden getauscht: Resultat: 8 6 4 2 1 10 3 5 7 9
10 > 3 wahr: 10, 3 werden getauscht: Resultat: 8 6 4 2 1 3 10 5 7 9
10 > 5 wahr: 10, 5 werden getauscht: Resultat: 8 6 4 2 1 3 5 10 7 9
10 > 7 wahr: 10, 7 werden getauscht: Resultat: 8 6 4 2 1 3 5 7 10 9
10 > 9 wahr: 10, 9 werden getauscht: Resultat: 8 6 4 2 1 3 5 7 9 10
Ende 1. Lauf (Neue Folge: 8 6 4 2 1 3 5 7 9 10)

Wir haben nun die größte Zahl der Folge am Ende der Folge stehen.

2. Lauf
8 > 6 wahr: 8, 6 werden getauscht: Resultat: 6 8 4 2 1 3 5 7 9 10
8 > 4 wahr: 8, 4 werden getauscht: Resultat: 6 4 8 2 1 3 5 7 9 10
8 > 2 wahr: 8, 2 werden getauscht: Resultat: 6 4 2 8 1 3 5 7 9 10
8 > 1 wahr: 8, 1 werden getauscht: Resultat: 6 4 2 1 8 3 5 7 9 10
8 > 3 wahr: 8, 3 werden getauscht: Resultat: 6 4 2 1 3 8 5 7 9 10
8 > 5 wahr: 8, 5 werden getauscht: Resultat: 6 4 2 1 3 5 8 7 9 10
8 > 7 wahr: 8, 7 werden getauscht: Resultat: 6 4 2 1 3 5 7 8 9 10
8 > 9 falsch: 8, 9 werden nicht getauscht: Resultat: 6 4 2 1 3 5 7 8 9 10
9 > 10 falsch: 9, 10 werden nicht getauscht: Resultat: 6 4 2 1 3 5 7 8 9 10

Wir haben nun die zweitgrößte Zahl der Folge am vorletzten Ende der Folge stehen.
(In unserem Beispiel steht gleichzeitig die drittgrößte Zahl der Folge am vorvorletzten Ende)
usw...
Quellcode zu Übung 13, Aufgabe 2:
/*
$DATE (19.01.2001)
$AUTH Lars Ehrhardt
$VER  1.0
 */

import java.util.*;

class bubblesort {
    public static void main(String arguments[]){
        int [] unsortfeld = new int[14];
        int [] sortfeld = new int[unsortfeld.length];

        unsortfeld = belegung(unsortfeld); // Zufallsfolge erstellen

        System.out.print("unsortierte Eingabefolge: ");
        for (int i = 0; i < unsortfeld.length; i++)
            System.out.print(unsortfeld[i] + " ");
        System.out.println();

        sortfeld = bubblesort(unsortfeld); // Folge sortieren

        System.out.print("sortierte Eingabefolge: ");
        for (int i = 0; i < sortfeld.length; i++)
            System.out.print(sortfeld[i] + " ");
        System.out.println();
    }

    /* bubblesort
       Übergabeparameter: unsortiertes Array int[]
       Rückgabeparameter: sortiertes Array int[]

       Optimierung des ursprünglichen Algorithmus:
       1. Die 2. For-Schleife wird bei jedem Durchgang 1x weniger
          ausgeführt, da wir nach dem 1. Durchgang das grösste Element
          am Ende der Folge stehen haben, beim 2. Durchgang das
          grösste und das zweitgrösste Element, usw.
       2. Ausserdem bricht die 1. For-Schleife ab, sobald keine Zahlen
          in einem Durchgang vertauscht werden.

      Hinweis: Das Array wird hier anscheined call-by-reference
               übergeben. Das unsortierte Array geht also nach der
               Sortierung verloren!
     */

    static int [] bubblesort(int[] sortfeld) {

        boolean vertauscht;

        for(int j = 0; j < sortfeld.length; j++) {
            vertauscht = false;
            for (int i = 0; i < sortfeld.length-1-j; i++) {
                if (sortfeld[i] > sortfeld[i+1]) {
                    int feldspeicher;
                    feldspeicher = sortfeld[i];

                    sortfeld[i]   = sortfeld[i+1];
                    sortfeld[i+1] = feldspeicher;
                    vertauscht = true;
                }
            }
            if (vertauscht == false) break;
        }
        return(sortfeld);
    }

    /* belegung
       Übergabeparameter: Integerarray
       Rückgabewert: Integerarray mit Zufallszahlen

     */

    static int [] belegung (int[] feld) {
        Random r = new java.util.Random();
        for (int i = 0; i < feld.length; i++)
            feld[i] = r.nextInt() % 100;
        return feld;
    }
}


(Keine Garantie auf Richtigkeit!)
zurück zur Übersicht
News
12.10.: Seiten zum WS03 aktualisiert
02.09: Seite zum WLAN-Projekt aktualisiert
10.04: Seiten zum SS03 aktualisiert
12.08: Eigene Vorlage für Seminararbeiten der FH hinzugefügt
14.07: Informationen zum 5. Semester hinzugefügt.
14.07: Druckfunktion für die Seiten überarbeitet: Auflistung der Hyperlinks über Fußnoten realisiert.
04.06: Links für IT-Sec neu strukturiert
27.04: Projekte des SS02 hinzugefügt
07.04: Lehrveranstaltungen des SS02 hinzugefügt
07.04: Dokumentation zum X-Terminals Projekt
Navigation: [START] [00-ws] [prog] [p-java004.htm]
[print]  [e-mail]  [main]