Zum Menü springen.

Übungsblatt 5: Sortieren

Abgabe bis Mittwoch, 27. Mai, 10:00 Uhr!

Diese Aufgaben bauen auf der Klasse Menge auf, die eine mathematische Menge mit Hilfe eines internen Arrays implementiert. Gehen Sie in diesem Übungsblatt davon aus, dass dieses Array nicht sortiert ist.

Aufgabe 5-1

Formulieren Sie folgende Algorithmen präzise in „natürlicher Sprache“ nach Dr. Bürg.

  1. Bubble-Sort („sortieren durch Aufsteigen“)
  2. Insertion-Sort („sortieren durch Einfügen“)
  3. Selection-Sort („sortieren durch Auswählen“)

Aufgabe 5-2 *

Bearbeiten Sie mindestens eine der folgenden Teilaufgaben.

  1. Erweitern Sie die Klasse Menge mit einer Objektmethode void bubbleSort (), die den internen Array aufsteigend sortiert. Verwenden Sie den Bubble-Sort–Algorithmus.
  2. Erweitern Sie die Klasse Menge mit einer Objektmethode void insertSort (), die den internen Array aufsteigend sortiert. Verwenden Sie den Insertion-Sort–Algorithmus.
  3. Erweitern Sie die Klasse Menge mit einer Objektmethode void selectSort (), die den internen Array aufsteigend sortiert. Verwenden Sie den Selection-Sort–Algorithmus.

Aufgabe 5-3

  1. Erweitern Sie die Klasse Menge mit einer Objektmethode void recursiveSort (int beginn), die den internen Array aufsteigend sortiert. Verwenden Sie den nachfolgend angegebenen rekursiven Algorithmus.
  2. Welchem der iterativen Algorithmen der vorangegangenen Aufgaben entspricht dieser Algorithmus konzeptuell?

Gegeben: (Rest-)Array A (definiert durch das Array und den Index, an dem der Rest beginnt)

Start
falls A nicht leer ist
bestimme das kleinste Element in A sortiere den Rest von A
Stop

Zusatzaufgabe 5-4

  1. Erweitern Sie die Klasse Menge mit einer Objektmethode void collectionsSort (), die den internen Array aufsteigend sortiert. Verwenden Sie eine der Sortier-Methoden in java.util.
  2. Beurteilen Sie die Zeitkomplexität Ihrer Implementierung.
$Id: HEADER.html 2009-05-20 $
Icon  Name                                   Last modified      Size  Description
[DIR] Parent Directory                                            -   
[HTM] HEADER.html                            2023-10-11 10:00  2.9K  
[TXT] Loesung51.txt                          2023-10-11 10:00  1.4K  
[TXT] Loesung52.java                         2023-10-11 10:00  1.9K  
[TXT] Loesung53.java                         2023-10-11 10:00  1.3K  
[TXT] Loesung54.java                         2023-10-11 10:00  647   
[HTM] README.html                            2023-10-11 10:00  957