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

myGully.com (https://mygully.com/index.php)

- Programmierung (https://mygully.com/forumdisplay.php?f=67)

- - [JAVA] Char Array mit Bubblesort durch While-Schleife sortieren (https://mygully.com/showthread.php?t=2140185)

Belenus666

14.10.10 15:37

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

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 (Beitrag 21399030)

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 (Beitrag 21402343)

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 (Beitrag 21403400)

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 (Beitrag 21430057)

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 (Beitrag 21431620)

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 (Beitrag 21435947)

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.

Alle Zeitangaben in WEZ +1. Es ist jetzt 23:33 Uhr.