Hallo zusammen,
ich habe als erstes einen QuickSort-Algorithmus programmiert bei dem das Pivotelement in jedem Aufruf ganz rechts steht. Funktioniert auch soweit. Jetzt wurde mir die Aufgabe gestellt, einen QuickSort-Algorithmus zu erstellen bei dem das Pivotelement bei jedem Aufruf in der Mitte steht. Hier habe ich ein Problem
Mein zu sortierendes Array lautet: A = [3,4,7,10,6,8,1,9,2,5]
juti, das Pivotelement lautet: "6"
Code-Snippet:
[JAVA=42]
int A[] = {3,4,7,10,6,8,1,9,2,5};
public static void quicksort (int A[], int li, int re) {
if (li > re) return; /* Falls die ganz linke Position im Array
* kein Folgeelement mehr hat brich ab!
*/
else
{
int k; // Zaehlvariable
int l = 0; // Variable fuer den linken Zeiger
int r = re; // Variable fuer den rechten Zeiger
int tmp; // Variable fuer die Zwischenspeicherung beim Tausch
int pivot = A[(li+re)/2]; // Pivotelement
//-----------------------------------------------------------------------------------//
for (k=0; k<re; k++)
{
while (A[l] <= pivot) {l++;}
while (A[r] >= pivot) {r--;}
if (l>r) break;
else {tmp = A[l]; A[l] = A[r]; A[r] = tmp;}
}
[/code]
[JAVA=42]
quicksort(A,li,pivot-1);
quicksort(A,pivot+1,re);
[/code]
O.K. - wenn ich jetzt den Zeigerdurchlauf nachvollziehe, dann ergibt sich folgendes Bild:
"l läuft bis 7 - r bleibt bei 5" - Tausch
"l läuft bis 10 - r läuft bis 2" - Tausch
"l läuft bis 6 (Pivot) - r läuft bis 1" - ???
Hier ist mein erstes Problem, mein linker Zeiger kommt am Pivotelement an, rechter Zeiger hat aber noch Elemente vor sich.
Wird hier das Pivotelement dann mit dem Element des rechten Zeigers vertauscht?
ich habe als erstes einen QuickSort-Algorithmus programmiert bei dem das Pivotelement in jedem Aufruf ganz rechts steht. Funktioniert auch soweit. Jetzt wurde mir die Aufgabe gestellt, einen QuickSort-Algorithmus zu erstellen bei dem das Pivotelement bei jedem Aufruf in der Mitte steht. Hier habe ich ein Problem
Mein zu sortierendes Array lautet: A = [3,4,7,10,6,8,1,9,2,5]
juti, das Pivotelement lautet: "6"
Code-Snippet:
[JAVA=42]
int A[] = {3,4,7,10,6,8,1,9,2,5};
public static void quicksort (int A[], int li, int re) {
if (li > re) return; /* Falls die ganz linke Position im Array
* kein Folgeelement mehr hat brich ab!
*/
else
{
int k; // Zaehlvariable
int l = 0; // Variable fuer den linken Zeiger
int r = re; // Variable fuer den rechten Zeiger
int tmp; // Variable fuer die Zwischenspeicherung beim Tausch
int pivot = A[(li+re)/2]; // Pivotelement
//-----------------------------------------------------------------------------------//
for (k=0; k<re; k++)
{
while (A[l] <= pivot) {l++;}
while (A[r] >= pivot) {r--;}
if (l>r) break;
else {tmp = A[l]; A[l] = A[r]; A[r] = tmp;}
}
[/code]
[JAVA=42]
quicksort(A,li,pivot-1);
quicksort(A,pivot+1,re);
[/code]
O.K. - wenn ich jetzt den Zeigerdurchlauf nachvollziehe, dann ergibt sich folgendes Bild:
"l läuft bis 7 - r bleibt bei 5" - Tausch
"l läuft bis 10 - r läuft bis 2" - Tausch
"l läuft bis 6 (Pivot) - r läuft bis 1" - ???
Hier ist mein erstes Problem, mein linker Zeiger kommt am Pivotelement an, rechter Zeiger hat aber noch Elemente vor sich.
Wird hier das Pivotelement dann mit dem Element des rechten Zeigers vertauscht?