Wertbelegungstabelle? Was ist das?

[wikimione]

hallo liebe user!
mir wurde eine aufgabe gestellt: ich soll eine wertbelegungstabelle für eine quicksortimplementation erstellen
dummerweise weiß ich nicht was eine wert~ ist
des algorithmus zu schreiben war doch recht simpel
könnt ihr mir erklären was eine wertbelegungstabelle ist, und können wir sie gemeinsam entwickeln?
wäre sehr nett!

Delphi-Quellcode:

procedure Quick(var arr: array of Integer; left, right: Integer) ;
var
  Low, High, mid, hlp: Integer;
begin
  Low := left; 
  High := right;
  mid := arr[(Low + High) div 2];  

  repeat
    while arr[Low] < mid do Inc(Low) ; 
    while arr[High] > mid do Dec(High) ;
    if Low <= High then 
    begin
      hlp := arr[Low]; 
      arr[Low] := arr[High]; 
      arr[High] := hlp;
      Inc(Low) ;
      Dec(High) ;
    end;
  until Low > High;
  if High > left then Quick(arr, left, High) ;
  if Low < right then Quick(arr, Low, right) ; 
end;

dann sind noch 2 andere proceduren drin die zahlen erzeugen usw.

[marabu]

Herzlich willkommen in der Delphi-PRAXiS, wikimione.

Es ist keine Schande eine Aufgabenstellung zu hinterfragen. Die Bedeutung von Wertbelegungstabelle muss dir bereits einmal mitgeteilt worden sein, sonst disqualifiziert sich der Aufgabensteller. Frage ihn besser nochmal.

Ich verstehe darunter eine tabellarische Darstellung der Zustände, die der zu sortierende Vektor während des Sortierens einnimmt - nach jeder Veränderung eine neue Tabelle.

Freundliche Grüße

[wikimione]

Zitat:

Zitat von marabu

Herzlich willkommen in der Delphi-PRAXiS, wikimione.

Es ist keine Schande eine Aufgabenstellung zu hinterfragen. Die Bedeutung von Wertbelegungstabelle muss dir bereits einmal mitgeteilt worden sein, sonst disqualifiziert sich der Aufgabensteller. Frage ihn besser nochmal.

Ich verstehe darunter eine tabellarische Darstellung der Zustände, die der zu sortierende Vektor während des Sortierens einnimmt - nach jeder Veränderung eine neue Tabelle.

Freundliche Grüße

also: welche variable hat wann welchen wert?

[rotfc]

Zitat:

Zitat von wikimione

also: welche variable hat wann welchen wert?

Genau!

[wikimione]

wäre es möglich, dass ich es erst selbst versuche und ihr das ganze dann überprüft/ggf. berichtigt?
ich bin mir nämlich wirklich unsicher, da ich sowas nie gemacht habe...

[marabu]

Wenn du die Arbeitsweise der Prozedur Quick() erklären kannst, dann weißt du bereits, wo du den Aufruf Show(arr) einbauen musst um die Aufgabe zu erfüllen.

Fang erstmal an, dann sehen wir weiter.

[wikimione]

wenn show(arr) dafür da ist den momentanen zustand des arrays anzuzeigen würde ich ihn

Delphi-Quellcode:

if Low <= High then
    begin
      hlp := arr[Low];
      arr[Low] := arr[High];
      arr[High] := hlp;
      Inc(Low) ;
      Dec(High) ;
//hier
    end;

einbauen...

[marabu]

Ausgezeichnet - ich bin sicher, dass du nicht allzuviel Hilfe benötigen wirst.

[wikimione]

also ich habs mal probiert:

die zahlen im array arr: 10 5 8 9 27 13 28 30 1 50
Low=0
High=9
Mid=5
1. while schleife: low=5 (also zahl 27)
2. while schleife: high=8 (also zahl 1)
da low(5)<= high( 8 )
hlp=27 (arr[5])
arr[5](27):= 1 (arr[8])
arr[8](1):= hlp(27)
low=1
high=8

also müsste nach dieser umsortierung mein array wie folgt lauten:
10 5 8 9 1 13 28 30 27 50

haut das soweit hin?

€dit: sollte kein smiley sein :)

[marabu]

So drüber geschaut sieht das ganz korrekt aus.

Schreibe dir die Prozedur Show(), dann kannst du die Momentanwerte der einzelnen Array-Elemente visuell kontrollieren.

Du kannst auch mit dem Debugger schrittweise durch die Prozedur QuickSort() marschieren.

[wikimione]

show() sieht dann wahrscheinlich so aus, dass es mir immer arr, low, high und help ausgibt?
noch eine frage: das mid bleibt nach der ersten initialisierung immer beim selben wert?

ich hab zu haus leider kein delphi, ich versuchs daher auf dem trockenen:

Delphi-Quellcode:

procedure show();
var gesamt: string;

begin

gesamt:= 'low=' + Inttostr(low) +' ' + 'high='  Inttostr(high)+ 'array:' +Inttostr(arr[]);
ShowMessage(gesamt);

end;

[Matze]

Zitat:

Zitat von wikimione

noch eine frage: das mid bleibt nach der ersten initialisierung immer beim selben wert?

Du weist mid auch nur zu Beginn einen Wert zu, veränderst mid in der Schleife aber nicht mehr. Dann ist es klar, dass mid immer gleich bleibt. ;)

Edit: War wohl leichter Blödsinn. :oops:
Dass deine Funktion "Quick" heißt und du jedoch "QuickSort" aufrufst, brachte mich ein wenig durcheinander.

[marabu]

Nein, Show() sollte dir einfach immer das ganze Array ausgeben - denke ich. Dazu solltest du bei der Prozedur auch das Array als Parameter vorsehen und es beim Aufruf übergeben.

Delphi-Quellcode:

procedure Show(const a: TStringDynArray);
begin
  // your code here
end;

Und was den Wert von mid angeht: Der wird im laufenden Kontext nur einmal und meist willkürlich gewählt. Durch den rekursiven Aufruf ändert er sich dann, was zur schrittweisen Partitionierung des zu sortierenden Vektors führt.

Delphi zu Hause ist übrigens kein Problem, wenn du schnell genug angebunden bist: Der Turbo Delphi Explorer ist kostenfrei und für deine Bedürfnisse ausreichend und kann an verschiedenen Stellen (DP, CodeGear) heruntergeladen werden, wenn du keine Setup-CD aus einer Fachzeitung besitzt.

[wikimione]

riesen dicken fetten dank marabu (und matze) :D