Probl mit Array

[Xanatos]

Hallo,
wir haben heute in der Schule folgende Aufgabe gestellt gekriegt und ich kann sie einfach nicht lösen.
Es gibt ein Array 'Sift' die Größe (size) ist 10. Also das Array kann nur 10 Werte annehmen. Alle Variablen sind ganze Nummern. DIV ist ein Operator der die beiden Zahlen teilt und dann abrundet. Also 15 DIV 4 ist 3 und 19 DIV 2 ist 9.

hier der Code


size=10
sep=size DIV 2
WHILE sep>0
FOR count=1 TO size-sep
index=count
WHILE (index>0) AND [Sift(index)>Sift(index+sep)]
spare=Sift(index)
Sift(index)=Sift(index+sep)
Sift(index+sep)=spare
index=index-sep
ENDWHILE
NEXT count
sep=sep DIV 2
ENDWHILE


Die rot markierte Stelle verstehe ich überhaupt nicht, überhaupt die ganze Schleife, wäre nett wenn mir jemand die erklären kann.

Gegeben ist noch folgende Tabelle, die man auch ausfüllen muss:

Variablen-------------------//---------- Array Sift
sep-count-index-spare-size-//---1---2---3---4---5---6---7---8---9---10
-0--- 0-----0------0---10--//--103-64--18--7---144-83--15--37- 11--52


Ich hoffe ihr versteht was ich meine...
Wäre nett wenn ihr mir noch einen denksntoß gebt wie das funktioniert

[Marscel]

- Integer size wird der Wert 10 zugewiesen.
- Integer sep bekommt den Wert size DIV 2.

Solange sep größer als 0 ist:
Integer count ist 1, wird solange inkrementiert bis es den Wert size-sep erreicht hat (so wars zumindest bei BASIC):
- Integer index bekommt den Wert von count zugewiesen.
Solange index größer als 0 ist und der Wert von Sift[index] größer ist als der Wert von Sift[index+sep]:
- Integer spare bekommt den Wert von Sift[index] übergeben.
- Sift[index] bekommt den Wert von Sift[index+sep] zugewiesen.
- Sift[index+sep] bekommt den von spare gespeicherten Wert (also den alten Sift[index]).
- index gleich index - sep gerechnet.
Solange-Schleife Ende.
Nächster count.
- sep bekommt den Wert sep DIV 2.
Solange-Schleife Ende.

Der Vorgang in der tiefsten Schleife ist auf jeden Fall ein Tauschvorgang, wo die Werte des Index mit Index+Sep getauscht werden.

Sieht für mich schon fast nach einem Chiffer-Algoryhtmus aus. :|

[Neomi]

Das ist eine Art ShellSort. Ein recht effektiver Algorithmus, der das Array aufsteigend sortiert. Hier ist eine Doku zur Funktionsweise:
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shell.htm

Die rot markierte Stelle ist die mittlere von drei Zeilen, die zwei Werte im Array tauschen.

[Xanatos]

vielen dank, ich versuche das erstmal nachzuvollziehen, aber wie kommt man dann auf die werte für das Array?
Und, bei der letzten Schleife versteh ich das letzte Statement nicht, man weiß doch noch gar nicht ob Sift[index] größer ist als der Wert von Sift[index+sep]?


€dit: Also es ist schon basic...

Du hast ja gemeint count=0, ist das nicht 1?

[Marscel]

€dit: Also es ist schon basic...

Wirklich, dachte, es sei Delphi, aber mit nicht-C-Style Sprachen habe ich mich noch nicht beschäftigt.

Du hast ja gemeint count=0, ist das nicht 1?

Mein Fehler...

[Xanatos]

Also index ist dann ja auch 1?
Aber woher weiß man dann ob die dritte Schleife durchgeführt werden soll?
Weil man weiß ja die werte für das Array nicht?

€it:
Integer spare bekommt den Wert von Sift[index] übergeben.
- Sift[index] bekommt den Wert von Sift[index+sep] zugewiesen.
- Sift[index+sep] bekommt den von spare gespeicherten Wert (also den alten Sift[index]).
ISt das dann so, nehmen wir mal an, die WErte für Sift(1)=x und Sift(6)=y, das dann nach dieser Schleife, Sift(1)=y ist und Sift(6)=x?

[Marscel]

Das Array wird gar nicht erst angelegt, bzw. wenn man das nicht machen muss, werden ja nirgends Werte den Indizes zugeordnet.

Vielleicht muss du die erst manuell mit den Werte füllen, die du unter Array Sift selber gepostet hast:

1---2---3---4---5---6---7---8---9---10
103-64--18--7--144-83--15--37--11--52

EDIT, angenommen index ist 1 und sep ist 5, dann sieht das ganze ja so aus:

spare = Sift(1)
Sift(1) = Sift(1+5) ; d.h. Index 6
Sift(1+5) = spare

[Neomi]

Und, bei der letzten Schleife versteh ich das letzte Statement nicht, man weiß doch noch gar nicht ob Sift[index] größer ist als der Wert von Sift[index+sep]?

Das ist sogar sichergestrellt, immerhin ist es die Bedingung für die Schleife. Und ja, die drei Zeilen, die du meinst, bewirken einen Tausch zwischen den beiden Arrayeinträgen.

[Xanatos]

mhh ich denke schon andernfalls macht das ja keinen sinn..Jetzt bleibt nur noch die frage wie ich die Tabelle ausfüllen soll.

Also der Algorythmus geht ja so los, dass size=10 ist, und sep=5, das das ja größer ist als 0, wird die nächste Schleife durchgelaufen, also index=1 und dann die nächste, so dass spare=sift(1) ist und Sift(1)=Sift(6) und Sift(6)=spare. Also im Klartext heißt das, dass die werte einfach nur getauscht wurden, und vor der Schleife, sift(1)=83 war und nicht 103, richtig?
Die Schleife wird dann ja nicht mehr wiederholt, da der index negativ ist (-4), allerdings die 2 SChleife, korrekt?, sodass index=2 ist, dann die WErte wieder getauscht wurden, also vor der Schleife sift(2)=15 war und Sift(7)=64?
Ist das so richitg?