Übungsblatt 12a

Übungsblatt 12a

Sorting, Linked Structures

PI-1 2008/09

Assignment #1: Suchen und Sortieren

Die Effektivität von Such- und Sortieralgorithmen wird mit der erforderlichen Anzahl von Vergleichen bzw. Vergleichen und Vertauschungen beschrieben.
Gegeben sei ein Feld, das mit den natürlichen Zahlen 1 bis 8 beliebig gefüllt ist, wobei jede Zahl genau einmal vorkommt. Untersuchen Sie für die folgenden in der Vorlesung vorgestellten Algorithmen, welche Anfangsbelegung des Feldes zu minimaler bzw. maximaler Anzahl von Vergleichen und Vertauschungen führt. Geben Sie die ermittelten Anfangsbelegungen und die aus diesen Belegungen jeweils resultierende Zahl der Vergleiche und Vertauschungen an.

lineare Suche (Angabe des Feldes und der Zahl)
binäre Suche (Angabe des Feldes und der Zahl)
Insert-Sort
Quicksort mit mittlerem Element als Pivot-Element

Assignment #2: Performance

Ein Programm erhalte N Datensätze als Eingabe, die es daraufhin verarbeitet. Es wurden 4 Testläufe mit unterschiedlich vielen Datensätzen (d.h. unterschiedlichen Werten für N) gemacht und dabei folgende Laufzeiten gemessen:

N Laufzeit

1000 5 Sekunden

2000 20 Sekunden

5000 2 Minuten

10,000 8 Minuten

Mit welcher Laufzeit müssten wir rechnen, wenn wir das Programm mit N = 100,000 vielen Datensätzen aufrufen? Kreuzen Sie die (eine) Antwort an:

____ Wenige Minuten ____ Wenige Stunden ____ Ein halber Tag

____ Mehrere Tage ____ Mehrere Wochen

Formulieren Sie Ihre Hypothese bezüglich der Programmlaufzeit als Formel in N.

Assignment #3: Liste

Definieren Sie eine Klasse StringList, mit der eine Liste von String-Objekten aufgebaut werden kann. Die Operationen zum Einfügen in die Liste sollen dabei so definiert werden, dass die Liste stets lexikographisch sortiert ist. Die Operationen zum rekursiven Umkehren der einfach verketteten Liste sollen so definiert werden, dass der Kopf das neue Ende und das Ende der neue Anfang wird. Alle Verweise werden dabei gedreht. Die Klasse sollte mindestens Methoden bieten, die folgendes Programm ermöglichen:

class ListDemo {
   public static void main(String args[]){

      if (args.length == 0){
         System.err.println("Wenigstens ein Argument nötig");
         return;
      }

      StringList list = new StringList(args[0]);
      StringList reversedList;

      for (int i = 1; i < args.length; i++)
         list = list.insert(args[i]);
         reversedList = reverse(list);
         while (list != null){
            System.out.println(list.getValue());
            list = list.next();
         }
         while (reversedList != null){
            System.out.println(list.getValue());
            list = list.next();
         }
      }
}

Assignment #4: Linked Structures:

Unten stehen die Java-Methoden f(), g(), h(), sowie graphische Repräsentationen von verketteten Datenstrukturen A, B, C, D. Jede der drei Methoden x(),y(),z() ist dazu geeignet, eine oder mehrere der Datenstrukturen A,B,C,D nach einem Wert key zu durchsuchen. Schreiben sie zu jeder der Datenstrukturen A,B,C,D jeweils in die linke obere Ecke die Namen der Funktionen, also f(), g(), oder h(),die zum Durchsuchen dieser Datenstruktur und dem Auffinden des Wertes key geeignet sind.

Bemerkung 1: Der Hilfs-Typ Node ist wie folgt definiert:

public class Node {
public int key;
public Node left, right;
}

Bemerkung 2: Die Klassen-Variable start ist mit einem Wert vom Typ Node vorinitialisiert.

public boolean f(int key) { Node x = start; while (x != null) { if (x.key == key) return true; x = x.right; } return false; }	public boolean g(int key) { Node x = start; while (x != null) { if (x.key == key) return true; if (x.key > key) x = x.left; else x = x.right; } return false; }
public boolean h(int key) { Node x = start; while (true) { x = x.right; if (x.key == key) return true; if (x == start) break; } return false; }

N	Laufzeit
1000	5 Sekunden
2000	20 Sekunden
5000	2 Minuten
10,000	8 Minuten