Bobsort
Bob schlägt ein neues Sortierverfahren vor, um ein Array von paarweise verschiedenen Zahlen (beginnend bei Index 0) zu sortieren. Die Idee ist simpel: Wir beginnen bei Position pos=0 und ermitteln für das Element an Position pos die Anzahl der kleineren Elemente im Array (z.B. 17). Dies bedeutet, dass das Element pos an Stelle 17 des sortierten Arrays bewegt werden muss. Wir tauschen also das Element pos mit dem Element an Stelle 17, und verfahren mit dem neuen Element an Stelle pos weiter. Jedes mal wenn das Element an Position pos korrekt ist (d.h. es existieren genau pos kleinere Elemente), inkrementieren wir pos.
Implementieren Sie das Verfahren in Java. Führen Sie die Methode runTest() für verschiedene Array-Größen durch. Haben Sie anhand dessen eine Abschätzung für die Komplexität?
package de.hsrm.ads;
import java.util.Random;
public class BobSort {
public static void swap(int[] a, int pos1, int pos2) {
int tmp = a[pos1];
a[pos1] = a[pos2];
a[pos2] = tmp;
}
public static void sort(int[] a) {
// FIXME: implement
}
// immer dieselben Pseudozufallszahlen!
private static final Integer DEFAULT_SEED = Integer.valueOf(654321);
public static int[] createRandomArray(int n) {
int[] a = new int[n];
for (int i=0; i<n; ++i)
a[i] = i;
// shuffle randomly.
Random rand = new Random(DEFAULT_SEED*n);
for (int i=0; i<n; ++i) {
int pos = rand.nextInt(n);
swap(a, i, pos);
}
return a;
}
public static void runTest(int n) {
long startTime;
long endTime;
int[] a = createRandomArray(n);
startTime = System.currentTimeMillis();
sort(a);
endTime = System.currentTimeMillis();
System.out.format(
"[n=%d] : %d ms.\n",
n, (endTime - startTime));
}
public static void main(String[] args) {
}
}
Subato
