[JAVA] Char Array mit Bubblesort durch While-Schleife sortieren

Belenus666 · 14.10.10, 15:37

Ich sitze gerade im Technikum Porgrammieren und stehe total auf m Schlauch.
Wenn jemand von euch weiß wie ich folgende Aufgabe lösen kann bin ich euch echt dankbar.
Auch für Denkanstöße jeglicher Art bin ich dankbar.

Code:

class While {
// Demonstrate While loop.
public static void main ( String args[] ) {
int[] F = {90,91,92}; 
int i; // declare loop counter 
System.out.println("Start program...");
i = 0; // initialize loop counter (= array index)
while (i <= 2) // loop variable still in range?
{
System.out.println(F[i]); // display value
i = i + 1; // increment loop counter
}
System.out.println("Program finished");
}}

Aufgabe:
2. Modify the program While to use the length property of an array.
Declare the array F to have 6 elements of type character.

3. Implement bubblesort for a character array of at least 6 elements.
Display the elements before sorting and after every change in the array.
Think about the best way to display what your program is doing.
Initialize the array appropriately to test your program.

You may use only WHILE and IF-THEN-ELSE for program control!
The loop statements FOR and DO are not allowed! VERBOTEN!
Use comments to describe what your program does.

4. Extend your bubblesort solution to count how many times the inner loop is
executed, and how many times elements are swapped.

Bis jetzt hab ich:

Code:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package bubblesort;

/**
 *
 * @author eulric
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        char[] F = {'a','c','b','e','d','f'};
int i; // declare loop counter

System.out.println("Start program...");

i = 0; // initialize loop counter (= array index)


while (i <= 5) // loop variable still in range?
{
System.out.println(F[i]); // display value
i = i + 1; // increment loop counter
}
System.out.println("Program finished");

    }
}

LG
Belenus

germgerm · 14.10.10, 20:34

jetzt fehlt fast nur noch bubblesort ^^
schau dir den pseudocode bei wikipedia an.

Poppers · 15.10.10, 07:47

Grundsätzlich steckt ja nicht so viel dahinter wenn gleich man zugeben muss dass man hier und da stolpern kann. Meine Frage, was ist deine Frage? Oder soll ich dir den Code jetzt runter schreiben?

Schwierigkeiten seh ich eigentlich nur bei der Kasakadierung der Schleifen für den Bubblesort. Besonders beim Vergleich von zwei chars. Denn was ist größer a oder b? Um das sauber zu lösen musst du den char in einen Hex-Wert wandeln. (Zuordnung ASCII Tabelle).

Wenn du den Bubblesort richtig verstanden hast, weist du das maximal n*(n-1)/2 Durchläufe notwendig sind um dein Array im "Worst-Case" zu sortieren. Vielleicht hilft dir das etwas bei der Implementierung.

Wenn du noch Fragen hast, Frag! Ansonsten würd ich dir empfehlen einfach mal Code zu implementieren und hier zu posten. Ich sag dir dann schon ob der Gedankengang richtig ist bzw wie die Umsetzung ausschaut.

Falls ich nit Antwort schreib kurz PN die gibts bei mir direkt aufs Handy

Lg

Kapp.Sparda · 15.10.10, 08:56

Zitat:

Zitat von Poppers

Schwierigkeiten seh ich eigentlich nur bei der Kasakadierung der Schleifen für den Bubblesort. Besonders beim Vergleich von zwei chars. Denn was ist größer a oder b? Um das sauber zu lösen musst du den char in einen Hex-Wert wandeln. (Zuordnung ASCII Tabelle).

Schwierigkeiten gibts da eigentlich nicht, man kann Buchstaben genauso wie Zahlen vergleichen. Umwandeln muss man ansich nichts man muss nur wissen was wo in der ASCII Tabelle liegt um zu wissen was größer ist.

Man kann sich zB auch einfach die ASCII Werte mit nem kleinen Typecasting ausgeben lassen:

Code:

System.out.print((int)'a'); // liefert die Dezimalzahl 97
System.out.print((int)'b'); // liefert die Dezimalzahl 98

Somit kann man sagen b ist "größer" a.

Hier mal ein BubbleSort Code von der java-uni.de

Code:

public class BubbleSort { 
   public static void sortiere(int[] x) {
      boolean unsortiert=true;
      int temp;
      
      while (unsortiert){
         unsortiert = false;
         for (int i=0; i < x.length-1; i++) 
            if (x[i] > x[i+1]) {                      
               temp       = x[i];
               x[i]       = x[i+1];
               x[i+1]     = temp;
               unsortiert = true;
            }          
      } 
   }

Musst eigentlich ja nur den Datentyp deines Arrays ändern und vielleicht die Vergleichsoperatoren umkehren; weiß ich jetz nich ^^

mfg

Xalir · 15.10.10, 13:12

Ich habe mich noch nie so richtig mit Java beschäftigt aber was mir auffällt:

Zitat:

2. Modify the program While to use the length property of an array.

Code:

while (i <= 5) // loop variable still in range?

wäre wohl besser so zu schreiben

Code:

while (i <= F.length) // loop variable still in range?

urga · 15.10.10, 16:34

Zitat:

Code:

public class BubbleSort { 
   public static void sortiere(int[] x) {
      boolean unsortiert=true;
      int temp;
      
      while (unsortiert){
         unsortiert = false;
         for (int i=0; i < x.length-1; i++) 
            if (x[i] > x[i+1]) {                      
               temp       = x[i];
               x[i]       = x[i+1];
               x[i+1]     = temp;
               unsortiert = true;
            }          
      } 
   }

das ist fast bubblesort.
warum? weil die innere for schleife immer über das komplette array geht, obwohl nach jedem scheifendurchlauf der zu sortierende teil um 1 element abnimmt.

PornoPenner · 15.10.10, 21:15

!

Kapp.Sparda · 16.10.10, 08:18

@urga: Das ist schon Bubblesort, nur finde ich diesen Algorithmus effektiver da er aufhört zu sortieren wenn alles sortiert ist während der Algorithmus mit zwei for-Schleifen Feldgröße² Durchläufe hat, also weitersortieren will selbst wenn schon alles sortiert ist.
Gerade bei Großen Arrays finde ich diese Version praktischer.

urga · 16.10.10, 12:56

Zitat:

Zitat von PornoPenner

Bsp:

99 05 06 07 08 09 01

--> 1. Runde Bubblesort: 05 99 05 07 08 01 09

nach einem durchlauf durch die for-scheife: 05 07 08 01 09 99.
die 99 muss bei weiteren durchgängen nicht mehr beachtet werden.

PornoPenner · 16.10.10, 13:15

Schon richtig, ich hab mich vertan.

PornoPenner · 16.10.10, 13:20

Zitat:

Zitat von Kapp.Sparda

@urga: Das ist schon Bubblesort, nur finde ich diesen Algorithmus effektiver da er aufhört zu sortieren wenn alles sortiert ist während der Algorithmus mit zwei for-Schleifen Feldgröße² Durchläufe hat, also weitersortieren will selbst wenn schon alles sortiert ist.
Gerade bei Großen Arrays finde ich diese Version praktischer.

Urga hat schon Recht.
Von zwei for-Schleifen hat er auch gar nicht gesprochen.
Die Abbruchbedingung ist bei BubbleSort immer die gleiche... ist die Liste sortiert, dann darf der Algorithmus abbrechen, sonst wäre es kein übliches BubbleSort.

Bei jedem Durchlauf ist das größte Element immer am Ende (es steigt wie ein Bläßchen nach oben... daher ja auch der Name). Daher muss nicht nach jedem DL die gesamte Liste überprüft werden.

Belenus666 · 19.10.10, 14:15

So LEute danke für eure Tipps ihr habt mir echt super geholfen^^
Wenn ich am Donnerstag wieder in Programmieren sitze poste ich euch mal eine Lösung.

Vllt findet ja noch jmd was was man besser machen kann^^

Thx an alle

So far Belenus

Belenus666 · 22.10.10, 12:10

So hier jetzt das komplette Prog

Code:

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package bubblesortwhile;

/**
 *
 * @author eike
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        char[] F = {'3', 'c', '2', 'b', '1', 'a'};
        int swa = 0;
        int inner = 0;
        int i; // declare loop counter

        System.out.println("Start program...");

        i = 0; // initialize loop counter (= array index)

        while (i < F.length) // loop variable still in range?
        {

            System.out.println(F[i]); // display value

            i = i + 1; // increment loop counter

        }

        System.out.println("Sortierung beginnt");

        i = 1;                              // Deklaration der i variable mit Wert 1
        while (i < F.length) {              //1. While_Schleife mit Bedingung i kleiner Arraylänge
            int j = F.length - 1;           //Initialisierung und Deklaration der Variable j mir größe Arraylänge -1
            while (j >= i) {                // Während j größer gleich i
                if (F[j] < F[j - 1]) {      // wenn F[j] kleiner F[j-1]
                    char temp = F[j];       // Initialisierund und Wertezuweisung Variable Temp = F[j]
                    F[j] = F[j - 1];        //Kopieren von Wert F[j-1] auf Wert F[j]
                    F[j - 1] = temp;        // Kopieren von Wert Temp auf F[j-1]
                    swa++;                  //Inkrementieren der Variable swa
                }
                inner++;                    //Inkrementieren der Variable inner
                j = j - 1;                  //Dekrementieren der Variable J
            }
            i = i + 1;                      //Inkrementieren der Variable I
        }

        i = 0;                              // initialize loop counter (= array index)

        while (i < F.length)                // loop variable still in range?
        {

            System.out.println(F[i]);       // display value

            i = i + 1;                      // increment loop counter

        }
        System.out.println("Die Zahlen wurden " + swa + " mal vertauscht"); //Ausgabe der Vertauschungen
        System.out.println("Die innere Schleife wurde " + inner + " mal durchlaufen");//Ausgabe der Inneren Schleifen Durchläufe
        System.out.println("Programm beendet!");//Ausgabe Programm Ende

    }
}

PornoPenner · 22.10.10, 15:37

Zitat:

Zitat von Belenus666

So hier jetzt das komplette Prog

... mit einer großen Anzahl von Design-Fehlern

Aber funktional wohl korrekt.

Belenus666 · 22.10.10, 16:16

Wie gesagt für Anregungen wie man was besser machen kann bin ich immer dankbar.

PornoPenner · 22.10.10, 17:21

Sehe grad, dass die Abbruchbedingung fehlt. So hat die Implementierung ja immer Worst-case-Laufzeit.

urga · 22.10.10, 18:38

Zitat:

Zitat von PornoPenner

Sehe grad, dass die Abbruchbedingung fehlt. So hat die Implementierung ja immer Worst-case-Laufzeit.

jupp. aber für nen anfänger im großen und ganzen ok.

evntl. eine sperate methode die das array ausgibt. z.b.

Code:

static void printCharArray (char[] a) {
 for (char c : a) {
  System.out.println(c);
 }
}
// oder als generische methode
public static<T> void printArray (T[] a) {
 for (T elem : a) {
  System.out.println (elem);
 }
}

Xalir · 23.10.10, 17:07

Ein bissl off-topic:

Warum man immer noch BubbleSort als ersten Sortieralgorithmus lehrt, ist jenseits meines Verständnisses. Das ist so ziemlich der naivste Algorithmus, den ich kennengelernt habe.

Andere Algorithmen, die nicht wesentlich schwieriger zu implementieren sind, schlagen BubbleSort selbst im worst-case um Längen.

urga · 23.10.10, 21:52

a) der ist so simpel, daß auch anfänger ihn selbst lösen können.
b) man kann auch relativ leicht verstehen, das er in O(n²) liegt.
c) somit auch einen guten einstieg in die komplexitätstheorie bietet, was zur frage führt, ob man das sortieren nicht effizienter hin bekommen kann, was dann zu
d) den effizienteren algorithmen führt.

PornoPenner · 23.10.10, 23:40

Zitat:

Zitat von Xalir

Ein bissl off-topic:

Warum man immer noch BubbleSort als ersten Sortieralgorithmus lehrt, ist jenseits meines Verständnisses. Das ist so ziemlich der naivste Algorithmus, den ich kennengelernt habe.

Andere Algorithmen, die nicht wesentlich schwieriger zu implementieren sind, schlagen BubbleSort selbst im worst-case um Längen.

Das ist eine typische Praktiker-Frage.
Ein Praktiker versteht eben nicht warum man etwas lernt, was man praktisch nie einsetzen wird.
Für ihn ist das nutzloses Wissen, wie die ganze Theorie.