nocheine quicksort frage

TheAxeEffect · Beiträge: 37

hi leute,
sorry, dass ich euch schon wieder behellige, aber mir ist nochwas aufgefallen, und das bereitet mir kopfzerbrechen^^:

ich hab den code aus meinem letzten thread für mich lesbarer gemacht(habe aber den algo NICHT verändert- er funktioniert noch immer), und beim genauen durchdenken sind mir einige dinge aufgefallen:
hier erstmal der code:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:

procedure RQSort(von,bis: Integer);
  var
    rechts, links: Integer;
    pivot: Integer;
    dreieck: Integer;
  begin



    pivot := A[von + Random(bis - von)];


    links := von;
    rechts := bis;
    while links<=rechts do begin
      while A[links] < Pivot do Inc(links);
      while A[rechts] > Pivot do Dec(rechts);
      if links <= rechts then
      begin
        dreieck := A[links];
        A[links] := A[rechts];
        A[rechts] := dreieck;
        Inc(links);
        Dec(rechts);
      end;
    end;
    if von < rechts then RQSort(von, rechts);
    if links < bis then RQSort(links, bis);
  end;

begin
  RQSort(Low(A), High(A)); 
end;

nun zu meinen fragen:
eigentlich müsste das doch so funktionieren oder:
man hat ne liste: von der wählt man irgendwie ein pivot-element aus...danach geht man erstmal vom anfang an die liste durch, bis man was findet, das größer ist, als das pivot-element. dann geht man vom ende nach vorne durch, und sucht nen kleineres element. dann vertauscht man die beiden, und macht so weiter. wenn die zwei dinger mit denen man sucht sich treffen, müsste man das pivot-element doch in die mitte von denen setzen, sonst wäre ja die liste nicht anständig in zwei teile geteilt..also nen kleineren und nen größeren..ich kann aber in meinem code NICHT erkennen, dass sowas passiert...dh. da is was faul oder?
und zur zweiten frage: wenn ich statt

markieren

Delphi-Quelltext

1:
2:

 if von < rechts then RQSort(von, rechts);
    if links < bis then RQSort(links, bis);

das da:

markieren

Delphi-Quelltext

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

 if von < rechts then begin 
bis:=rechts;
RQSort;
end;
    if links < bis then begin
von:=links;
 RQSort;
end;

schreibe, und die funktion einfach RQsort; nenne(ohne die klammern ), und von und bis als allgemeine variablen deklariere, und nicht in der funktion sozusagen, läuft der algo falsch...das versteh ich auch nich ganz^^
mfg und danke im vorraus,
simon

Narses · Verfasst: Mo 13.08.07 19:59

Moin!

TheAxeEffect hat folgendes geschrieben:

man hat ne liste: von der wählt man irgendwie ein pivot-element aus...

Das ist der Knackpunkt bei Quicksort: die "Güte" des Pivot-Elements entscheidet, wie das konkrete (Teil-)Feld (vor-)sortiert wird. Optimal wäre ein Element, das wertmäßig genau in der Mitte der im (Teil-)Feld vorkommenden Werte liegt. Da man das aber nur durch einen weiteren (also zusätzlichen) Durchlauf wirklich sicherstellen könnte, macht man das nicht, denn damit wäre der "Effekt" von Quicksort (nämlich O(nlogn)) wieder kaputt... deshalb ist dein Random() in der Auswahl des Pivot-Elements genau genommen Zeitverschwendung, denn es ist für die Güte des Elements unerheblich, also kannst du auch gleich das Element in der Mitte des Feldes nehmen und hoffen, dass es halbwegs gut ausgewählt ist. :arrow:

markieren

Delphi-Quelltext

1:	pivot := A[(von + bis) div 2]; // geht schneller als Random()!

TheAxeEffect hat folgendes geschrieben:

danach geht man erstmal vom anfang an die liste durch, bis man was findet, das größer ist, als das pivot-element. dann geht man vom ende nach vorne durch, und sucht nen kleineres element. dann vertauscht man die beiden, und macht so weiter. wenn die zwei dinger mit denen man sucht sich treffen, müsste man das pivot-element doch in die mitte von denen setzen, sonst wäre ja die liste nicht anständig in zwei teile geteilt..also nen kleineren und nen größeren..ich kann aber in meinem code NICHT erkennen, dass sowas passiert...dh. da is was faul oder?

Das hast du noch nicht korrekt durchdacht, bitte nochmal versuchen.

Das Pivot-Element ist nach dem Durchlauf einer Rekursionsebene automatisch in der Mitte der (Teil-)Folge! :mahn:

Kuckst du auch mal hier :les:

TheAxeEffect hat folgendes geschrieben:

und zur zweiten frage: wenn ich statt

markieren

Delphi-Quelltext

1:
2:

if von < rechts then RQSort(von, rechts);
  if links < bis then RQSort(links, bis);

das da:

markieren

Delphi-Quelltext

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

if von < rechts then begin 
  bis:=rechts;
  RQSort;
end;
if links < bis then begin
  von:=links;
   RQSort;
end;

schreibe, und die funktion einfach RQsort; nenne(ohne die klammern ), und von und bis als allgemeine variablen deklariere, und nicht in der funktion sozusagen, läuft der algo falsch...das versteh ich auch nich ganz^^

Na, da haben wir aber im Unterricht gepennt, als der Lehrer Rekursion erklärt hat, was... ?!

Die Parameter der Funktion sind Werteparameter, d.h. es werden in jeder Rekursionsinstanz der Sortierprozedur "neue" (lokale) Variablen dafür angelegt - und benötigt! Weil, sonst funktioniert es eben nicht... :lol:

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

TheAxeEffect · Beiträge: 37

also dass sich die variablenwerte bei ner rekursion ändern müssen ist mir schon klar, aber ich versteh diese schreibweise nicht ganz^^. kannst du mir sagen, was an meinem code anders is? so wie ich das verstehe bedeuet
RQSort(von, bis); nichts anderes, als dass dise prozedur mit den variablen von und rechts ausgeführt wird...am anfang sind dise variablen Low(A) und length(A) also das erste und letzte element der liste...
und rqsort(von,rechts)bedeuetet für mich(was offenbar falsch ist), dass die variable "von" so bleibt wie sie ist, und dass die variable "bis" den wert von "rechts" einnimmt...wär nett, wenn du mir sagen könntest, wo da mein denkfehler ist,da ich, wie du sicher unschwer erkennen kannst, ein anfänger bin, und die syntax eben noch nich so gut kenne^^.

und: warum rückt bei dem code, den ich gepostet habe, das pivot element in die mitte.
angenommen unsere liste sieht so aus:
>5(pivot)3 9 2 9 9 2< ...
von links ist die erste zahl die er findet die neun....von rechts isses die zwei..kk, dann vertauscht er beide:
5(pivot) 3 2 >2 9< 9 9
dann findet er rechts noch ne neun, und links garnix mehr...aber das pivotelement steht nicht in der mitte...hm...da ich hier offenbar auch nen denkfehler gemacht habe, wäres nett, wenn du mir dne auch aufzeigen würdest^^
mfg,
simon
edit: dass, das mit dem randompivot nicht ganz so toll is weiß ich selber^^.
aber ist die mitte auch ein unfug, da es viel leichter wäre zb. das erste element zu nehmen(die berechung der mitte dauert ja auch). das einzige was man sich überlegen könnte, wäre es, sich zb. die ersten 5 zahlen anzusehen, und von denen die mittlerste zu nehmen..in ner richtig böse langen liste, würde dies sicher eine performancesteigerung bringen, aber bei kürzeren eher nen performancerückgang glaub ich.
werd dann eh sowas noch einbauen, will mich aber erst mit dem algo selber beschäftigen, bevor ich ihn optimiere^^
ps: vielen dank für dein verständis

Narses · Verfasst: Di 14.08.07 00:50

Moin!

Pack mal ein Memo mit auf die Form und diesen zusätzlichen Code mit in die Prozedur:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

procedure RQSort(von,bis: Integer);
  var
    rechts, links: Integer;
    pivot: Integer;
    dreieck: Integer;
begin
  pivot := A[(von + bis) shr 1]; // geht noch schneller... ;)
  Memo1.Lines.Add('von:'+IntToStr(von)+', bis:'+IntToStr(von)+', Pivot:'+IntToStr(pivot));
  links := von;
  rechts := bis;
  while (links <= rechts) do begin
    while A[links] < Pivot do Inc(links);
    while A[rechts] > Pivot do Dec(rechts);
    if links <= rechts then begin
      dreieck := A[links];
      A[links] := A[rechts];
      A[rechts] := dreieck;
      Inc(links);
      Dec(rechts);
    end;
  end;
  if (von < rechts) then
    RQSort(von, rechts);
  if (links < bis) then

    RQSort(links, bis);
  end;
end;

Weitere Details zbgl. Quicksort findest zu z.B. hier. :les:

Das Thema Quicksort ist nun wirklich bis ins Details durchgekaut worden, das müssen wir sicher hier nicht auch noch 1000 mal tun...

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

TheAxeEffect · Beiträge: 37

hm..ich hab mal den algo ohne die rekursion durchgeführt(dh. ich ahbe die zeilen

markieren

Delphi-Quelltext

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

 if von < rechts then begin

     RQSort(von, rechts);
     end;
    if links < bis then begin

     RQSort(links, bis);

gelöscht, und mir dann das in nem memo ausgeben lassen...komisch war, dass das nur fast gestimmt hat..dh. es hat ausreißer gegeben...mit nem array mit 15 werten sah das so aus:
0
3
5
20
7
8
16
31
37
42
67
47
27
84
86
dh. dass das irgendwas nicht so geht, wie es sollte...
für sowas hilft mir der link, den du mir gepostet hast leider nicht viel weiter, aber danke trotzdem.

Narses · Verfasst: Di 14.08.07 01:39

Moin!

TheAxeEffect hat folgendes geschrieben:

hm..ich hab mal den algo ohne die rekursion durchgeführt
[...]
dh. dass das irgendwas nicht so geht, wie es sollte...

Merkwürdig aber auch

du entfernst aus einem rekursiven Algorithmus die Rekursion - und plötzlich funktioniert er nicht mehr... :roll:

(übrigens: das gleiche passiert, wenn du aus den Grenzen globale Variablen machst, s.o.)

TheAxeEffect hat folgendes geschrieben:

für sowas hilft mir der link, den du mir gepostet hast leider nicht viel weiter, aber danke trotzdem.

Doch, und wie er hilft - er zeigt dir, wie der Algorithmus wirklich funktioniert; mir ist nur einfach schleierhaft, was du da vor hast... :nixweiss:

glaubst du ernsthaft, du könntest den Quicksort-Algo noch optimieren - was Generationen von Informatikern vor dir bereits (mehr oder weniger erfolglos) getan haben und dabei einen entscheidenden Durchbruch erlangen?
Mein Tipp: ich vermute, du hast das Prinzip der Rekursion noch nicht verstanden. :idea:

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

TheAxeEffect · Beiträge: 37

naja, eigentlich müsste, wenn ich die rekursion entferne, eine liste vorliegen, die "halb" sortiert ist, dh. alle die kleiner als das pivot element sind links, das pivot element in der mitte, und die größeren rechts..das is aber nich der fall...müsste es bei quicksort aber sein oder?
@ rekursion: für mich is das folgendes:
eine sich immer wieder selbst aufrufende rechenoperation nach dem gleichen schema, die als ausgangspunkt das ergebnis des letzten durchganges verwendet...das stimmt doch oder?
edit:
ich ahbs mir ja gedacht^^
nach dem einfügen dieser zeilen, sieht die liste ohne rekursion richtig aus:

markieren

Delphi-Quelltext

1:
2:
3:

 dreieck2:=pivot;
    A[pivot]:=A[links] ;
    A[links]:=pivot;

wenn man es genau nimmt, war dieser code aus dem internet nicht quicksort, sondern was anderes, da quicksort nach dem durchlauf der ersten rekursionsebene zwei sortierte teillisten hat...was bei dem code nicht der fall war^^ naja, nun issees quicksort, und ich bin glücklich

ps: danke für dein verständis :-)

;

Narses · Verfasst: Di 14.08.07 12:42

Moin!

TheAxeEffect hat folgendes geschrieben:

naja, eigentlich müsste, wenn ich die rekursion entferne, eine liste vorliegen, die "halb" sortiert ist, dh. alle die kleiner als das pivot element sind links, das pivot element in der mitte, und die größeren rechts..das is aber nich der fall...

Da du das Pivot-Element und die unsortierte Folge in deinem Beispiel nicht angegeben hast, lässt sich das nun leider nicht mehr nachvollziehen...

TheAxeEffect hat folgendes geschrieben:

müsste es bei quicksort aber sein oder?

Ja, ist es auch; kannst du mit meinem Visualisierungs-Tool aus dem Link weiter oben auch schön beobachten.

TheAxeEffect hat folgendes geschrieben:

@ rekursion: für mich is das folgendes:
eine sich immer wieder selbst aufrufende rechenoperation nach dem gleichen schema, die als ausgangspunkt das ergebnis des letzten durchganges verwendet...das stimmt doch oder?

Najaaaa, fast.

Zum einen hat das nicht zwangsweise was mit Rechnen zu tun, zum anderen fehlt mir da die Abbruchbedingung in deiner Beschreibung, und zum Schluss sind die berechneten Werte - wenn es denn schon um Rechnen geht - nicht zwangsweise Werteparameter. :nixweiss:

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

TheAxeEffect · Beiträge: 37

hab meinen letzten beitrag editiert...jetzt geht die funktion richtg^^
edit:
also ohne diese zeilen (tausch "Link" und "pivot") ging das nicht. kannst sogar selber versuchen, ich schwörs dir, es geht nur mit denen. is auch logisch, wenn man sich überlegt, was der algo eigentlich macht.
mfg,
simon
so. ich erkläre mein problem nun offiziell als gelöst^^ :-)

;
achja: und vielen dank, und entschuldige, dass ich dir auf die nerven gegangen bin

Narses · Verfasst: Di 14.08.07 13:17

Moin!

Das hier:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

  procedure QuickSort(l, r: Integer);
    var
      i, j, hilf,
      Pivot: Integer;
  begin
    Pivot := F[(l +r) div 2];
    i := l;
    j := r;
    repeat
      while (F[i] < Pivot) do
        Inc(i);
      while (Pivot < F[j]) do
        Dec(j);
      if (i <= j) then begin
        hilf := F[i];
        F[i] := F[j];
        F[j] := hilf;
        Inc(i);
        Dec(j);
      end;
    until (i > j);
    if (l < j) then
      QuickSort(l,j);
    if (i < r) then
      QuickSort(i,r);
  end;

ist ein garantiert funktionierender Quicksort. Und wenn ich mir mal den Dreieckstausch ansehe, dann kommt bei mir das Pivotelement nicht drin vor, denn:

TheAxeEffect hat folgendes geschrieben:

is auch logisch, wenn man sich überlegt, was der algo eigentlich macht.

Also was auch immer du da "testest", denk nochmal drüber nach...

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.

TheAxeEffect · Beiträge: 37

ne, das ist ein funktionierender sortieralgorithmus, aber nicht genau QUICKSORT. zwar sehr ähnlich, aber bei quicksort ist das pivot-element nach dem ersten durchgang in der mitte, was bei diesem algo NICHT der fall ist. kannste ja teste, indem du die rekursion entfernst, und dir das ergebnis ansiehst. wenn du meinen algo nimmst, wirste zwei unterschiedl. große teillisten vorfinden, bei dem da NICHT.
mfg,
simon

Narses · Verfasst: Di 14.08.07 13:47

TheAxeEffect hat folgendes geschrieben:

ne, das ist ein funktionierender sortieralgorithmus, aber nicht genau QUICKSORT.

Was ist es denn, "Narses-Sort"? :gruebel:

Wenn du doch schon alles weißt, warum fragst du dann hier noch?

_________________
There are 10 types of people - those who understand binary and those who don´t.

-Pl- · Beiträge: 22 Win XP, Win Vista Delphi 7

Ich glaube er hat nur noch nicht verstanden, dass bei Quicksort das Pivot-Element am Ende nicht unbedingt in der Mitte stehen muss.

TheAxeEffect · Beiträge: 37

ich weiß, dass das nict sein muss, damit der algo GEHT, aber der quicksort is nunmal so definiert^^

TheAxeEffect · Beiträge: 37

argh, ich bin ein depp. hab nen satz aus wiki nich richtig gelesen...ich gebs zu, ich hatte unrecht, es ist egal wo das pivot-element steht.
sorry,
simon

alzaimar · Verfasst: So 26.08.07 14:00

Narses hat folgendes geschrieben:

Moin!

TheAxeEffect hat folgendes geschrieben:

man hat ne liste: von der wählt man irgendwie ein pivot-element aus...

Das ist der Knackpunkt bei Quicksort... deshalb ist dein Random() in der Auswahl des Pivot-Elements genau genommen Zeitverschwendung, denn es ist für die Güte des Elements unerheblich, also kannst du auch gleich das Element in der Mitte des Feldes nehmen und hoffen, dass es halbwegs gut ausgewählt ist. :arrow:

markieren

Delphi-Quelltext

1:	pivot := A[(von + bis) div 2]; // geht schneller als Random()!

Der Vorteil eines zufällig ausgewählten Pivot-Elementes ist der, das man kein Worst-Case angeben kann (obwohl es ihn natürlich gibt): Daher wird die Random-Variante in der Literatur durchaus als theoretisch brauchbare Alternative angegeben.

_________________
Na denn, dann. Bis dann, denn.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme