Algorithmus gesucht: Array sortieren, mit drei Werten

Beginner

Friday, June 1st 2007, 9:43am

Algorithmus gesucht: Array sortieren, mit drei Werten

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

Professional

Posts: 378

Friday, June 1st 2007, 10:13am

öhm... zum sortieren würde ich mir mal bubblesort ansehen...
hier der link zu wiki

http://de.wikipedia.org/wiki/Bubblesort

thx, truespin

Molt

Beginner

Posts: 3

Friday, June 1st 2007, 10:38am

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

Master

Posts: 1,134

Friday, June 1st 2007, 12:34pm

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

Beginner

Posts: 3

Friday, June 1st 2007, 5:15pm

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

Master

Posts: 1,134

Friday, June 1st 2007, 6:15pm

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

Professional

Posts: 630

Friday, June 1st 2007, 7:01pm

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ß

Professional

Posts: 217

Friday, June 1st 2007, 8:49pm

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?