Implementieren Sie eine Variante von InsertionSort, die jede neue Zahl in einen von rechts wach- senden sortierten Bereich einfügt, wie in der folgenden Darstellung illustriert:
Leiten Sie Ihre Methode von der Klasse Sort ab. Führen Sie Ihr Programm aus (es wird ein Korrektheitstest anhand verschiedener Zufalls-Arrays wachsender Größe durchgeführt). Beheben Sie eventuelle Fehler. Ersetzen Sie dann sämtliche Vergleiche und Änderungen des Ziel-Arrays durch Aufrufe der Methoden
lt(),
lte(),
gt(),
gte(),
swap(),
move() und
set(). Ersetzen Sie z.B.
xs[i] = xs[i+1] durch
move(a, i, i+1), oder
if(xs[i]>xs[j]) durch
if(gt(xs,i,j)). Hierdurch wird die Anzahl der benötigten Vergleiche und Änderungen mitgezählt und in der Konsole ausgegeben. Für Details schauen Sie sich bitte die Kommentare in der Klasse Sort an.
package de.hsrm.cs.ads;
public class InsertionSort extends Sort{
@Override
public void sort(int[] xs) {
}
public static void main(String[] args){
InsertionSort sort = new InsertionSort();
sort.runSmall(100000);
}
}
Subato
