Entwickler-Ecke :: Thema anzeigen - quicksort:max. Anzahl rekursiver Aufrufe

fuggaz - So 25.05.08 15:07
Titel: quicksort:max. Anzahl rekursiver Aufrufe

Hallo,
Problem ist folgendes:
Ich programmiere nicht in Delphi und kann deshalb keine functions benutzen.
Deshalb kann ich auch nicht einfach rekursiv programmieren.
Als Lösung habe ich dann einen Array eingeführt, in dem die Werte immer gespeichert werden und dann wieder entsprechend an der richtigen Stelle ausgelesen werden.
Das klappt auch alles und er sortiert auch richtig.

Nun weiß ich aber nicht wie groß ich den Array machen muss.
Es ist doch so, dass bei Quicksort max n^2 Vergleiche nötig sind.
Ich brauche die aber nicht, sondern die max. Anzahl an rekursiven Aufrufen, da dann jedesmal Werte gespeichert werden.
Ich habe jetzt erstmal den Array n^2 groß gemacht aber ich würde das gerne reduzieren.

Wie kann ich das ausrechnen?
oder ist es einfach n^2-n?

Gausi - So 25.05.08 15:28

Womit programmierst du denn, und was ist das für ne Sprache die keine Funktionen bzw. Prozeduren kennt? Sowas gibts doch eigentlich überall, oder nicht?

Zur Frage: Afaik ist das abhängig von dem Ausgangsarray und der Wahl des Pivot-Elements. Wirklich vorhersagbar ist das glaube ich nicht.

fuggaz - So 25.05.08 20:46

Ach ja jetzt kommt der (hoffentlich richtige) Geistesblitz.
Im Worst-Case würde ich immer eine leere Liste erstellen.
Und somit n^2-1 mal rekursiv aufrufen.
Schade, schade^^
Dann kann ich max 22 Zahlen sortieren...
Danach wäre n^2>511 und das ist die Arraygrenze...

alzaimar - So 25.05.08 21:13

Ich verstehe deinen Ansatz nicht: Wenn Du Quicksort iterativ implementieren willst, dann machst Du das mit einem Stack, auf dem die (L,R)-Grenzen der zu sortierenden Teilliste abgelegt werden. Im ungünstigsten Fall sind das maximal ca. N (-2, denke ich) Elemente, wenn nämlich die Liste absteigend sortiert ist.

fuggaz - So 25.05.08 21:48

Ich weiß nicht ob man das iterativ nennt was ich gemacht habe, aber es ist so:
Ich habe die rekursive Funktion aus Delphi genommen und dort wo die Funktion sich wieder selbst aufruft speichere ich die zwei benötigten Werte.
Wenn ich jetzt irgendwann aus dieser Schleife rauskomme lese ich sie wieder aus.
Wie mir grad auffällt(vllt ja jetzt richtig^^) müssten es doch max 2n-1 Aufrufe sein, denn:
1.Der erste zählt nicht;-) -> -1
2.n-mal wird "links" aufgerufen
3.n-mal wird "rechts" aufgerufen
Also bei jedem erfolgreichen "linken" Aufruf gibt es einen nicht erfolgreichen "rechten" Aufruf(bsp).
Da ich nur von dem einen Aufruf speichere fallen n-mal weg.
=>n-1

Du kommst auf n-2. Wie das?

Quelltext

1:
2:
3:
4:
5:
6:
7:

 funktion quicksort(links, rechts)
     falls links < rechts dann
         teiler := teile(links, rechts)
         quicksort(links, teiler-1)
         quicksort(teiler+1, rechts)
     ende
 ende

ub60 - So 25.05.08 21:50

alzaimar hat folgendes geschrieben:

Es sollten etwa 2N Elemente sein (L+R).

alzaimar hat folgendes geschrieben:

Im ungünstigsten Fall sind das maximal ca. N (-2, denke ich) Elemente, wenn nämlich die Liste absteigend sortiert ist.

Das kommt auf die Wahl des Pivot-Elements an. Anfang oder Ende sind dabei (siehe Dein Bsp.) sehr ungünstig.

ub60

alzaimar - So 25.05.08 22:09

ub60 hat folgendes geschrieben:

Es sollten etwa 2N Elemente sein (L+R).

Jupp, ich meinte (L,R)-Tupel

ub60 hat folgendes geschrieben:

Das kommt auf die Wahl des Pivot-Elements an.

Nein. Egal, welches Du nimmst, bei einer sortierten Liste ist eine Teilliste immer 2 Elemente groß, und wenn die auf den Stack kommt, haben wir eben 2*(N-2) Elemente auf dem Stack:

Die Liste hat 3 Elemente: Wir benötigen also maximal eine Teilliste mit 2 Elementen. 2= (3-2)*2. q.e.d.
Bei 4 Elementen (a,b,c,d) haben wir maximal 2 Teillisten auf dem Stack: (a,c),(a,b), 4= (4-2)*2. stimmt also auch.

Das ist zwar kein Beweis, ich denke aber, das es klar ist.

@fuggaz: Du kannst einen Aufruf (den 1.) rausnehmen. Schau Dir mal TStringList.Quicksort in der 'Classes' Unit an.

ub60 - So 25.05.08 22:42

@alzaimar:
Irgendwie aneinander vorbeigeredet. Nichts gegen Deine Zahl :wink:
Meine Bemerkung bezog sich auf den worst case eines umgekehrt sortierten Arrays.
Wenn ich da als Pivot-Element das Element aus der Mitte nehme, ist das Array nach dem ersten Durchlauf (fast) sortiert. Für diesen Fall ein worst-case-array zu generieren, ist schon etwas schwieriger.

ub60

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!