blubberl12
Grünschnabel
Dabei seit: 06.06.2016
Beiträge: 1
 |
|
| Quicksort Insertion Sort Hybrid |
     |
Meine Frage:
Hallo zusammen,
ich muss folgende Aufgabe bearbeiten:
Modi?zieren Sie den in der Vorlesung besprochenen Quicksort-Algorithmus, sodass ab einer (vorher festgelegten) Teilproblemgröße von m Elementen nicht mehr rekursiv verfahren wird, sondern insertion sort aufgerufen wird. Bestimmen Sie experimentell einen (für Ihre Implementierung) geeigneten Wert von m und dokumentieren Sie Ihre Vorgehensweise hierbei.
Meine Ideen:
Den Quicksort-Algorithmus habe ich entsprechend abgeändert und füge ich unten ein. Ich komme aber einfach nicht darauf wie ich m bestimmen soll. Ich habe immer wieder gelesen, dass das 9 oder 10 sein müsste. Da ich aber zeigen muss, wie ich darauf komme, habe ich versucht mir die Laufzeit für verschiedene size-Werte in Nanosekunden anzeigen zu lassen. Das kommt aber zu Werten in Millionenhöhe (mal davon abgesehen, dass sich die Laufzeit hardwareabhängig immer wieder verändert). In Millisekunden lag der Wert immer zwischen 2 und 6.
public class Quicksort {
public static void main (String args[]){
long startTime = System.nanoTime();
Quicksort q = new Quicksort();
int[] a = new int[100];
fillArray(a);
quicksort(a, 0, a.length-1);
for (int i = 0; i < a.length; i++){
System.out.println(a[i]);
}
long endTime = System.nanoTime();
long totalTime = endTime - startTime;
System.out.println(totalTime);
}
public static int[] quicksort(int[] a, int L, int R) {
int m = a[(L + R) / 2];
int i = L;
int j = R;
int size = (R+1) - L;
if (size <= 10) {
insertionSort(a);
}
else{
while (i <= j) {
while (a[i] < m) i++;
while (m < a[j]) j--;
if (i <= j) {
swap(a, i, j);
i++;
j--;
}
}
if (L < j) quicksort(a, L, j);
if (i < R) quicksort(a, i, R);
}
return a;
}
public static void swap (int[] a, int i, int j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public static int[] insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int tmp = a[i];
int j = i - 1;
while ((j >= 0) && (tmp < a[j])) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = tmp;
}
return a;
}
private static void fillArray(int[] a) {
java.util.Random r = new java.util.Random();
for (int i=0; i<a.length; i++) {
a[i] = r.nextInt(a.length) + 1;
for (int k=0; k<i; k++) {
if (a[i] == a[k]) {
i--;
break;
}
}
}
}
}
Über Vorschläge würde ich mich sehr freuen! 
|
|
