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.