Selection Algorithmus

[Astasor]

hey

Was macht der Selection Algorithmus? Auf Wikipedia steht, das er die kth kleinste nummer sucht. nach der order statistik. (also min, max und range)

Selection algorithm - Wikipedia, the free encyclopedia

wenn ich was in den algorithmus übergebe, bekomme ich was zurück?

das minimum, maxium die "range" oder alles drei zusammen, oder das was am nächsten liegt?

stehe da i-wie vollkommen auf dem schlauch.

[Klotzkopp]

wenn ich was in den algorithmus übergebe, bekomme ich was zurück?

Du übergibst die Liste mit den Werten und ein k, und bekommst die k-te Ordnungsstatistik (also den k.-kleinsten Wert).

Das Minimum bekommst du für k=1, das Maximum für k=Anzahl der Werte.

[Astasor]

danke für deine antwort, klotzkopp

also ist k der rang des gesuchten elements?

was hat es mit dem k-kleinsten element auf sich? kann an einem k mehr als ein element definiert sein?

mfg astasor

Bearbeitet 13. Dezember 2010 von Astasor

[Klotzkopp]

also ist k der rang des gesuchten elements?

Der statistische Rang ist nicht wohldefiniert, wenn es Duplikate gibt. Ansonsten kommt das hin.

was hat es mit dem k-kleinsten element auf sich? kann an einem k mehr als ein element definiert sein?

Nein. Stell dir einfach vor, du sortierst die Elemente aufsteigend und schaust dann nach, was an Position k steht.

[Astasor]

Nein. Stell dir einfach vor, du sortierst die Elemente aufsteigend und schaust dann nach, was an Position k steht.

aber warum sagt man dann k.-kleinsten wert? denn wenn es einen k.-kleinsten wert gibt, müsste es ja auch einen k.-größten wert geben. klingt zumindest so.

mfg Astasor

[Klotzkopp]

aber warum sagt man dann k.-kleinsten wert?

Warum nicht? Was ist daran unklar? Kleinster, zweitkleinster, drittkleinster, ..., k.-kleinster. Wenn du dich an dem Begriff störst, dann sag eben k-te Ordnungsstatistik.

denn wenn es einen k.-kleinsten wert gibt, müsste es ja auch einen k.-größten wert geben. klingt zumindest so.

Natürlich. Aber der lässt sich ja ganz einfach auf einen k.-kleinsten zurückführen.

[Astasor]

Warum nicht? Was ist daran unklar? Kleinster, zweitkleinster, drittkleinster, ..., k.-kleinster

ich verstehe nicht, wie es an einem element unter k mehrere kleinste geben kann.

oder ist es so gemeint? also auf die ganze liste gesehen...

k=1 kleinster

k=2 zweitkleinster

k=3 drittkleinster

.

.

.

mfg Astasor

[Klotzkopp]

ich verstehe nicht, wie es an einem element unter k mehrere kleinste geben kann.

Kann es nicht. Wie kommst du darauf. Deine diesbezügliche Frage habe ich doch mit nein beantwortet. Oder habe ich dich da falsch verstanden?

Mal ein Beispiel. Liste L: {3,0,1,4,3,0,2}

k   Selection(L,k)

1   0

2   0

3   1

4   2

5   3

6   3

7   4[/code]

[Astasor]

ich hatte deine antwort falsch interpretiert.

die darstellung mit der liste ist gut und erklärend und ich denke, ich habs verstanden. sollte noch was sein, frage ich nochmal und ich hoffe, das ich wieder ne antwort bekomme.

Vielen Dank, Klotzkopp

mfg Astasor