Algorithmen[6]#1

[Johann]

Ich habe da mal eine Frage zur a):

Die partition()-Funktion nimmt ja ein Pivot-Element entgegen, sorgt aber angeblich dafür, dass keine leere Liste auftritt - wie genau passt das denn zusammen? Wenn ich in der b) etwa meine Matrikelnummer nehme und als Pivot-Element einfach die größte Zahl nehme, wird doch zwangsläufig eine Liste leer. Wäre es da nicht gescheiter, wenn man der Funktion einfach kein Pivot übergibt und sie sich das selber vernünftig aussuchen darf? Oder muss ich mir das so vorstellen, dass die Funktion halt ein "ungeschickt" gewähltes Pivot-Element korrigiert?

Edit: Wer lesen kann... okay bei der b) steht ja da wie man vorgeht, aber an der Problematik bei der a) ändert das ja nichts. Wozu übergebe ich ein Pivot bzw. wie soll ich das auswählen - wenn die partition()-Funktion eh vernünftige Werte zurückgibt?

[Chrisss]

in der übung heute wurde gesagt, dass man eine solche mögliche partition-funktion, welche die geforderten eigenschaften hat, bereits in der vorlesung gesehen hatte. Und zwar bei der Array-Implementierung von quicksort dieser repeat-until teil
das klappt schon so, du bekommst halt eine 1-elementige partition in dem genannten fall, mit dem pivot drin

[Chris]

oder du guckst dir das hier an

http://en.wikipedia.org/wiki/Selection_ ... _algorithm

[Johann]

Mh ich begreife das nicht ganz. Ich hab eben einen Algorithmus aufgestellt, der fast aussieht wie der von Wikipedia, nur ist meine Abbruchbedingung, dass ich irgendwann eine Partition mit nur noch einem Element habe. Partitionierungsbedingung war <= p. Bei der Wikipedia wird da ja irgendwie geschaut ob der neue Pivot-Index gleich k ist. Das funktioniert doch nur, wenn teilweise sortiert wurde, oder so.

Beispiel (mit fast meiner Matrikelnummer )

Code: Alles auswählen

l = 1
r = 7
a = [1 4 6 0 6 1 7]

Nun wird part., mit p = 1 und Bedingung eben <= p (und stabil!)

a = [1 0 1] [4 6 6 7]
Wobei i auf die 4 zeigt.

Da wir ja das 3. kleinste Element wollen, müssen wir ja offensichtlich links weitersuchen. Und genau da hakts dann. Wenn ich weiterhin das 1. Element nehme, ändert sich an der Menge gar nichts mehr... :D Was ich mir nun gedacht habe: Wir gehen ja von ner supertollen partition()-Funktion aus - schadet es dem Algorithmus wenn ich mal <= und mal < nehme? Ich meine wenn ich hier jetzt plötzlich um eine rechte leere Liste zu vermeiden restriktiver werde hätte ich

a = [0] [1 1] [...]

wobei ich gerade merke, dass hier dann endgültig Endstation ist. Mist.

[salami]

Da wir ja das 3. kleinste Element wollen

So wie ich es verstanden habe, muss das Element mit dem Rang 3 nicht das 3. kleinste Element sein.
Z.B.
arr[] = {1, 1, 2, 1, 1}
select(arr, 1) = 1
select(arr, 2) = 1
select(arr, 3) = 1
select(arr, 4) = 1
select(arr, 5) = 2
Somit würde es bei dir auch funktionieren.
Bin mir aber nicht sicher. Kann das vielleicht jemand bestätigen?

[Thomas]

also wenn du damit meinst dass für k = 3 bei 1 1 1 2, 1 rauskommt würde ich dir zustimmen. johann bei deinem algorithmus würdest du dann ja jetzt im zweiten array weiter suchen und hast dann zwei arrays mit jeweils einem wert, da ja nie eine leere partition zurückgegeben wird, wenn ich die aufgabenstellung richtig verstehe. partition muss man aber ja eh nicht selber implementieren oda? man kann doch einfach davon ausgehen dass die funktion die gewünschten eigenschaften hat und dann damit arbeiten oda?

[Chrisss]

die partition-funktion kann man als gegeben betrachten, ja, würd ich auch so sagen