AuD Übung 10 (Sortierverfahren)

Gruppennummer und Namen der Gruppenmitglieder (Zeilenformat!)

Punkte:

Total

Ausgabe: 31.1.2026

Abgabe: 8.2.2026

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

In dieser Übung sollen verschiedene Sortieralgortihmen implementiert und getestet werden. Wir verwenden Arrays. Die Laufzeit soll gemessen werden und mit den "theoretischen" Werten (Komplexitätsklasse) verglichen 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 Anweisungssequenz verwendet werden:

int[] x = new int[N];
for(int i=0;i<N;i++) x[i]=Math.ceil(1000*Math.random()));

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 1. 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: Klasse Sort (websh0)

import java.lang.*;
import uj.lang.*;
public class Sort {
  int [] data;
  public Sort(int [] data) {
    // Das Array data muss hier KOPIERT werden, sonst 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
    System.out.println("TODO");
  }
  // Hilfsfunktionen
  public void swap(int i,int j) {

  }
  public void insertSort(int dir) {
    System.out.println("insertSort");
    if (dir<0) {} // absteigend
    else       {} // aufsteigend
  }
  public void selectSort(int dir) {
    System.out.println("selectSort");
    if (dir<0) {} // absteigend
    else       {} // aufsteigend
  }
  public void bubbleSort(int dir) {
    System.out.println("bubbleSort");
    if (dir<0) {} // absteigend
    else       {} // aufsteigend
  }
}

Lösung.

VEJB

Aufgabe 2. Teste mit 10 randomisierten Datensätzen alle drei Algorithmen. Notiere die Ergebnisse: 1. Die Laufzeit, 2. Die Anzahl der VM ops (opsN). Wie verhalten sich die Algorithmen zueinander bezüglich der Rechnezeit und Anzahl der Rechenoperationen? Ist der Quotient aus beiden konstant?

Die Testklasse Test 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. (websh0)

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

Lösung.

VEJB

Test der Klasse Sort. Ausführung von make (Linux, Mac) oder makew (Windows) und run. (websh0)

Type help or hit TAB for a list of commands.

Eintrag der Messergebnisse für 10 Versuche mit jeweils neuen Daten. Die 11. Zeile soll den Mittelwert enthalten, N muss bei allen Versuchen gleich sein. (sS: selectSort, iS: insertSort, bS:bubbleSort)

Anhang Profiling

Nachfolgend ist ein Template für das Profiling eines Codeabschnitts (d.h.hier die relevanten algorithmischen Teile).


  public static void profileMe() {
    // Delta stop-start! 

    int [] ops = uj.lang.RT.profileOps();
    int [] mem = uj.lang.RT.profileMem();
    System.out.println(uj.lang.RT.profileTime()+" ms");
    System.out.println(uj.lang.RT.profileIcount()+" Instr.");
    System.out.println("SP="+uj.lang.RT.profileSp());
    System.out.println("[opALU="+ops[0]+" opBRANCH="+ops[1]+" opCALL="+ops[2]+" opNEW="+ops[3]+" opRET="+ops[4]+"]");
    System.out.println("[heapAlloc="+mem[0]+" nalloc="+mem[1]+" nfree="+mem[2]+" ngc="+mem[3]+" ncompact="+mem[4]+"]");  
  }
  ...
  uj.lang.RT.profileStart();
  // Hier der Code 1 für die Profilierung

  uj.lang.RT.profileStop();
  profileMe();
  uj.lang.RT.profileStart();
  // Hier der Code 2 für die Profilierung

  uj.lang.RT.profileStop();
  profileMe();
  ...

Hilfe

Created by the NoteBook Compiler Ver. 1.41.3 (c) Dr. Stefan Bosse (Mon Feb 02 2026 09:12:14 GMT+0100 (Central European Standard Time))