Hallo ihr Lieben,
Kann mir jemand helfen?
Hier die Aufgabenstellung, bloss der fettgeschriebene Teil:
Überlegen Sie: Wie oft etwa wird bei d) im Falle von n = 500'000 ein bestimmtes Zeichen (z.B. a) im zu sortierenden Array vorkommen? Wir haben also eine Situation mit vielen gleichen «Keys» (vgl. Input)! Optimieren Sie den Quicksort-Algorithmus wie empfohlen so, dass neu auch Datenelemente, welche gleich wie das Trennelement sind, vertauscht werden. Dazu ist nur eine ganz marginale Code-Anpassung erforderlich! Damit sollten wir eine optimalere Trennung und somit weniger rekursive Methodenaufrufe haben, d.h. auch eine kürzere Laufzeit erreichen. Ist dem so? Wie lange dauert jetzt das Sortieren von 500'000 Zeichen? Es macht wiederum Sinn, mehrmals die Sortierzeiten für ein- und dieselbe Ausgangslage zu messen.
Ich habe folgenden Code und weiss nicht, wie ich die gewünschte "marginale" Optimierung vornehmen soll:
Kann mir jemand helfen?
Hier die Aufgabenstellung, bloss der fettgeschriebene Teil:
Überlegen Sie: Wie oft etwa wird bei d) im Falle von n = 500'000 ein bestimmtes Zeichen (z.B. a) im zu sortierenden Array vorkommen? Wir haben also eine Situation mit vielen gleichen «Keys» (vgl. Input)! Optimieren Sie den Quicksort-Algorithmus wie empfohlen so, dass neu auch Datenelemente, welche gleich wie das Trennelement sind, vertauscht werden. Dazu ist nur eine ganz marginale Code-Anpassung erforderlich! Damit sollten wir eine optimalere Trennung und somit weniger rekursive Methodenaufrufe haben, d.h. auch eine kürzere Laufzeit erreichen. Ist dem so? Wie lange dauert jetzt das Sortieren von 500'000 Zeichen? Es macht wiederum Sinn, mehrmals die Sortierzeiten für ein- und dieselbe Ausgangslage zu messen.
Ich habe folgenden Code und weiss nicht, wie ich die gewünschte "marginale" Optimierung vornehmen soll:
package [I]A2[/I];
import [I]java.util.Random[/I];
public class [I]HigherSort [/I]{
[I]/**
* Vertauscht zwei bestimmte Zeichen im Array.
*
* @param a Zeichen-Array
* @param firstIndex Index des ersten Zeichens
* @param secondIndex Index des zweiten Zeichens
*/[/I]
private static final void exchange(final char[] a,
final int firstIndex,
final int secondIndex) {
char tmp;
tmp = a[firstIndex];
a[firstIndex] = a[secondIndex];
a[secondIndex] = tmp;
}
public static final void quickSort(final char[] a, final int left, final int right) {
int up = left; // linke Grenze nach oben bzw. rechts wandernd
int down = right - 1; // rechte Grenze (ohne Trennelement) nach unten bzw. links wandernd
char t = a[right]; // rechtes Element als TRENNELEMENT
boolean allChecked = false;
do {
while (a[up] < t) {
up++; // suche grösseres (>=) Element von links an
}
while ((a[down] >= t) && (down > up)) {
down--; // suche kleineres (<) Element von rechts an
}
if (down > up) { // solange keine Überschneidung
exchange(a, up, down);
up++; down--; // linke und rechte Grenze verschieben
} else {
allChecked = true; // Austauschen beendet
}
} while (!allChecked);
exchange(a, up, right); // Trennelement an endgültige Position (a[up])
if (left < (up - 1)) quickSort(a, left, (up - 1)); // linke Hälfte
if ((up + 1) < right) quickSort(a, (up + 1), right); // rechte Hälfte, ohne T’Elt.
}
public static void pr(final char[] a) {
[I]System[/I].out.print("(");
for (char i : a) {
[I]System[/I].out.print("" + i);
}
[I]System[/I].out.println(")");
}
public static void main([I]String[/I][] args) {
[I]Random [/I]r = new Random();
char[] c = new char[100];
for (int i = 0; i < c.length; i++) {
c[i] = (char) (r.nextInt(26) + 'a');
}
//char[] a = {'z', 'y', 'x', 'w', 'v', 'u', 't', 's', 'r', 'q', 'p', 'o', 'n', 'm', 'l', 'k', 'j', 'i', 'h', 'g', 'f', 'e', 'd', 'c', 'b', 'a'};
quickSort(c, 0,49);
pr(c);
}
}
