logo

 

 
 

 

 

 

 

 

 

Übersicht aller Übungen

  • Übung 1
  • Übung 2
  • Übung 3
  • Übung 4
  • Übung 5
  • Übung 6
  • Übung 7
  • Übung 8
  • Übung 9
  • Übung 10
  • Übung 11
  • Übung 12




    alle Lösungen (als *.zip)


  • Lösung Übung 1
  • Lösung Übung 2
  • Lösung Übung 3
  • Lösung Übung 4
  • Lösung Übung 5
  • Lösung Übung 6
  • Lösung Übung 7
  • Lösung Übung 8
  • Lösung Übung 9
  • Lösung Übung 10
  • Lösung Übung 11
  • Lösung Übung 12

  • Übung 1Übung 3

       

    Ü B U N G   2



    Aufgabe 1


    Bucket Sort: Bei Bucket-Sort handelt es sich um ein nicht vergleichsbasiertes Sortierverfahren. Hier werden z.B. Zahlen a1...an aus dem Bereich {0...N-1} dadurch sortiert, dass sie in durchnummerierte "Eimer" (Buckets) 0...N-1 geworfen werden. Die Inhalte dieser Eimer werden dann nacheinander ausgegeben, man erhält eine sortierte Folge.
    N gibt dabei den Wertebereich vor, d.h. es können Zahlenfolgen mit Werten von 0 bis N-1 sortiert werden.

    Beispiel:
    Zahlenfolge: 2 1 3 1 2 , N=4
    Wertebereich: N=4 => Zahlen mit den Werten 0 - 3 können sortiert werden. In der Zahlenfolge oben kommen Zahlen von 1 bis 3 vor, sie liegen also alle im Wertebereich.

    Nun werden nacheinander die Zahlen der Folge in die entsprechenden Eimer "geworfen":
    Die beiden Einsen landen in Eimer 1, die Zweien in Eimer 2 und die Drei in Eimer 3. Jetzt brauchen die Eimer nur noch in der richtigen Reihenfolge nacheinander ausgeleert werden.

    Schreiben Sie eine Klasse BucketSort, die die statische Methode sort und eine statische Variable N (Wertebereich) enthält. Die Methode sort soll ein int-array als Eingabeparameter erwarten und ebenfalls ein int-array zurückgeben.
    Testen Sie Ihre sort-Methode in der main-Methode mit den folgenden Werten:
    4, 2, 4, 28, 19, 255, 87, 0, 8, 103
    Wie groß muss N in diesem Fall mindestens gewählt werden?

    Visualisierung verschiedener Sortierverfahren

    Download der Lösung (BucketSort.java) (Java-Applet)

    Zusatzaufgabe



    Erweitern Sie die Klasse BucketSort um eine Methode sortChar, die diesmal ein Character-Array als Eingabeparameter erwartet bzw. ein Character-Array zurückgibt. Diese Methode soll nun nicht mehr nur Zahlen, sondern auch Buchstaben nach dem Bucket-Sort-Verfahren sortieren.

    Testen Sie diese Methode ebenfalls in der main-Methode. Was fällt Ihnen auf, wenn Sie eine Zeichenfolge sortieren, die sowohl Groß- als auch Kleinbuchstaben enthält?



    Aufgabe 2

    Der BubbleSort-Algorithmus kann dazu benutzt werden, eine Reihe von Zahlen in einem Array der Länge n zu sortieren. Bubblesort ist einer der einfachsten (aber auch langsamsten) Sortieralgorithmen und die Theorie ist verhältnismäßig einfach. Der Algorithmus führt folgende Schritte aus:
    1. Man durchläuft das gesamte Feld von vorne bis hinten n-1 mal.
    2. Man vergleicht die benachbarten Zahlen.
    3. Falls das linke Element größer ist als das rechte Element, sollen die beiden Zahlen vertauscht werden.

    Implementieren Sie BubbleSort in Java!

    Beispiel:

    Unsortiertes Array: [8,5,2,3]

    1. Durchlauf:
    Vergleich von 8 und 5 --> Vertauschen: [5,8,2,3]
    Vergleich von 8 und 2 --> Vertauschen: [5,2,8,3]
    Vergleich von 8 und 3 --> Vertauschen: [5,2,3,8]

    2. Durchlauf:
    Vergleich von 5 und 2 --> Vertauschen: [2,5,3,8]
    Vergleich von 5 und 3 --> Vertauschen: [2,3,5,8]
    Vergleich von 5 und 8 --> kein Vertauschen [2,3,5,8]

    3. Durchlauf:
    Vergleich von 2 und 3 --> kein Vertauschen: [2,3,5,8]
    Vergleich von 3 und 5 --> kein Vertauschen: [2,3,5,8]
    Vergleich von 5 und 8 --> kein Vertauschen: [2,3,5,8]

    Sortiertes Array: [2,3,5,8]

    Download der Lösung (BubbleSort1.java)


    Zusatzaufgabe

    Überlegen Sie sich, wie der BubbleSort-Algorithmus aus Aufgabe 1 verbessert werden könnte. Ist es nötig, in jedem Durchlauf das gesamte Feld zu durchlaufen ?

    Download der Lösung (BubbleSort2.java)
     
     
     

     

     


     
           
    © 2002 by Daniel Stojceski • Zylous@web.de