Algorithmus gesucht: Array sortieren, mit drei Werten

Molt · 1. Juni 2007, 09:43

Moin, Moin!

Soll ein Array sortieren, dass zwar beliebig viele Elemente enthalten kann, die sich allerdings nur aus drei Werten zusammensetzen.

Komm da irgendwie net klar, mit O(n) zu sortieren ...

Besten Dank schonmal im Voraus!

truespin · 1. Juni 2007, 10:13

öhm... zum sortieren würde ich mir mal bubblesort ansehen...
hier der link zu wiki^^ de.wikipedia.org/wiki/Bubblesort

thx, truespin

Molt · 1. Juni 2007, 10:38

Wie geschrieben brauche ich einen Algo, der in O(n) arbeitet ... und das geht denk ich mal nur, wenn er sich den speziellen Fall zu Eigen macht, dass es nur 3 verschiedene Werte gibt.
Beides erfüllt BubbleSort meines Wissens nach nicht.

edit:
glaub, ich hab da was gefunden

SoMeGuY · 1. Juni 2007, 12:34

O(n)? Es gibt einige Sortieralgorithmen die im Best Case (Array ist bereits sortiert) O(n) schaffen, im Average Case kannste das aber vergessen. Wer immer dir gesagt hast du sollst das machen, hat entweder keine Ahnung oder wollte dich verarschen. Auf Wikipedia findest du einen mathematischen Beweis, warum vergleichsbasiertes Sortieren nicht schneller geht als O(n*log(n)).

Ich würde dir MergeSort empfehlen, ein einigermaßen übersichtlicher Sortieralgorithmus (Divide-and-Conquer) der zwar nicht in-place arbeitet aber im Durchschnitt schneller ist als Quicksort, Laufzeit wäre dann in allen Fällen O(n*log(n))

Molt · 1. Juni 2007, 17:15

Huhu ... nicht immer so festgefahren denken

Ich schrieb doch, dass es nur Werte gibt:
1,2,3
a,b,c
rot,gelb,grün
italien,frankreich,deutschland
pizza,nudeln,bratmaxe
...

Da ist dann schon was in O(n) möglich ... hab aber wie gesagt glaub ich ne Lösung gefunden.
Zumal ich meinem Prof nicht gerne unter die Nase reiben würde, dass er keine Ahnung hat - auch wenn seine didaktischen Fähigkeiten net grad führend sind

SoMeGuY · 1. Juni 2007, 18:15

Ich verstehe deine Aufgabe nicht. Beliebig viele Werte oder nur drei? Was meinst du mit Zusammensetzen. Was für eine Idee hast du denn?

Aber davon abgesehen, wirst du es nur es nicht O(n) sortieren können, außer es ist bereits sortiert :!:

Hafner · 1. Juni 2007, 19:01

Darf ich mal fragen, was sein Sortierkriterium ist? Ist das überall gleich oder für jedes 3er-Array unterschiedlich?

Soll das Array, mit den 3er-Arrays auch sortiert werden?

Marcus Gnaß · 1. Juni 2007, 20:49

Ich glaube es handelt sich nicht um ein Array von 3erTupeln, sondern um ein Array von Elementen aus einer 3-er Menge. Oder hab ich das falsch verstanden?

Max123 · 8. Juni 2007, 14:15

Mich würde die Lösung noch interessieren...

Algorithmus gesucht: Array sortieren, mit drei Werten

Algorithmus gesucht: Array sortieren, mit drei Werten

Teilen

Tags