AuD Übung 10 (Sortierverfahren)

Gruppennummer und Namen der Gruppenmitglieder (Zeilenformat!)

Punkte:

Total

Abgabe: 7.2.2025

Es dürfen keine Standard Java Packages verwendet werden mit Ausnahme von System und String.

Der Java Code wird separat als klassisches natives Java Projekt abgegeben. Die wesentlichen Teile sollen aber zum Zwecke der Dokumentation hier in den Code Snippets eingetragen werden (unabhängig ob sie damit ausführbar sind oder nicht).

In dieser Übung sollen verschiedene Sortieralgortihmen implementiert und getestet werden.

Die Daten

Die Daten sollen in dieser Übung in Arrays gespcihert und randomisiert erzeugt werden (im Bereich 1-1000).

Algorithmus 1. Randomisierter Vektor (Gleichverteilung)

x=Array(N)
for(i=0;i<N;i++) x[i]=randint(1,1000)

In Java könnte z.B. folgende Anwieungssequenz verwendet werden:

Random random = new Random();
int[] x = new int[N];
for(int i=0;i<N;i++) x[i]=random.nextInt(1000);

Die Algorithmen

Sortieren durch Einfügen

function insertionSort(array) {
  for (i = 1; i < length(array); i++) {
    j = i;
    m = array[i];                                  m = array[i].key;
    // für alle Elemente links vom Marker-Feld
    while (j > 0 && array[j − 1] > m) {            .. array[j-i].key...
      // verschiebe alle größeren Elemente nach hinten
      array[j] = array[j − 1];
      j−− ;
    }
    // setze m auf das freie Feld
    array[j] = m;
  }
}

Sortieren durch Vertauschen (Bubble Sort)

function BubbleSort (array)
  // Eingabe: zu sortierende Folge F der Länge n
  do {
    swaps=0
    for (i=0;i<n;i++) { 
      if (array[i]> array[i + 1]) {
        swap(array,i,i+1)
        swaps++
      }
    }
  } while (swaps==0)
}

Sortieren durch Selektion

function swap (array,idx1,idx2) {
  t=array[idx1]
  array[idx1]=array[idx2]
  array[idx2]=t
}
function maxIndex(array,idx) {
  maxi=idx
  maxv=array[idx]
  for (var i=0;i<idx;i++) {
    if (array[i]>maxv) {
      maxi=i
      maxv=array[i]
    }
  }
  return maxi
}
function selectionSort(array) {
  p=length(array)-1
  while(p) {
    g = maxIndex(array,p)
    swap (array,p,g)
    p--
  }
}

Aufgabe. Implementiere die Klasse Sort. Die Sortierung soll aufsteigend und absteigend möglich sein (dir=+1,-1). Die Sortierfunktionen solle alle ihre Schleifendurchläufe zählen (auch in Hilfsfunktionen) und des Gesamtwert zurückgeben.

Die Sortierungklasse mit allen Drum und Dran

public class Sort {
  int [] data;
  int loopcount;
  public Sort(int [] data) {
    // Das Array data muss hier KOPIERT werden, sondt können die Algorithmen nicht mit
    // gleichen Daten verglichen werden
    this.data=new int[data.length];
    // copy
  }
  public void print() {
    // Ausgabe der Daten, getrennt durch Komma in Zeilen von je 10 Zahlen
  }
  // Hilfsfunktionen
  public void swap(i,j) {

  }
  public int insertSort(int dir) {
    loopcount=0;
    if (dir<0) // absteigend
    else       // aufsteigend
    return loopcount;
  }
  public int selectSort(int dir) {
    loopcount=0;
    if (dir<0) // absteigend
    else       // aufsteigend
  }
  public int bubbleSort(int dir) {
    loopcount=0;
    if (dir<0) // absteigend
    else       // aufsteigend
  }
}

Lösung.

VEJB

Aufgabe. Teste mit 10 randomisierten Datensätzen alle drei Algorithmen. Notiere die Ergebnisse: 1. Die Anzahl der Schleifendurchläufe, 2: Die Laufzeit. Was ist zu beobachten?

Die Testklasse mit randomisierter Erzeugung der Daten und der Zeitmessung. N ist mit 10 und 1000 zu ersetzen. Bei N=10 sollen die Eingabedaten und die Ausgabedaten angezeigt werden (zur Kontrolle). Wähle N größer wenn die mittlere Laufzeit kleiner als 10 ms ist.

public class Test {
  public static void main(String[] args) {
    int [] data = new int[N];
    int t0,t1;
    // Erzeugung der Daten s.o.
    for(int i=0;i<3;i++) {
      Sort sorter = new Sort(data);
      if (N<100 && i==0) sorter.print();
      t0=System.currentTimeMillis();
      switch (i) {
        case 0: sorter.insertSort(); break;
        case 1: sorter.selectSort(); break;
        case 2: sorter.bubbleSort(); break;
      }
      t1=System.currentTimeMillis();
      System.out.println(t1-t0);
      if (N<100) sorter.print();
    }
  }
}

Lösung.

VEJB

Eintrag der Messergebnisse für 10 Versuche mit jeweils neuen Daten. Die 11. Zeile soll den Mittelwert enthalten.

Created by the NoteBook Compiler Ver. 1.35.1 (c) Dr. Stefan Bosse (Fri Jan 31 2025 18:26:39 GMT+0100 (Central European Standard Time))