Sortieralgorithmus

[sk72]

Hallo,

Ich habe als Hausaufgabe folgende Aufgabe zu erledigen:

Ein gemischter Stapel aus 52 Spielkarten soll sortiert werden. Die Farben sollen in die
Reihenfolge Herz, Kreuz, Pik, Karo gebracht werden. Die Reihenfolge der Kartenwerte
sei 2, 3, 4, 5, 6, 7, 8, 9, 10, Bube, Dame, König, Ass. Die Farbe sei das st¨arkere
Sortierkriterium; eine Herz-Karte soll also immer vor einer Pik-Karte stehen.


Entwerfen Sie einen Algorithmus zum Sortieren der Spielkarten. Beschreiben Sie den
Algorithmus mit einfachen unmissverst¨andlichen S¨atzen. Es darf davon ausgegangen
werden, dass der Computer den Rang zweier Karten direkt vergleichen kann. D.h. f¨ur
zwei beliebige Karten (z.B. Pikbube und Karoneun) kann der Computer entscheiden,
welche Karte in der sortierten Folge zuerst erscheinen muss (im Beispiel der Pikbube).
Der Computer kann immer nur zwei Karten direkt vergleichen. Anweisungen wie “Finde
die niederwertigste noch ¨ubrige Karte” sind daher nicht erlaubt.

Jetzt habe ich mir Folgendes überlegt:

Ich erzeuge vier Arrays für Herz, Karo, Pik und Kreuz mit je 13 "Feldern" ?
Wenn ich nun eine Karte ziehe, dann soll sie dem entsprechenden Array zugeorndet werden und in das entsprechende Feld gesteckt werden.

Index 0 = 2
Index 1 = 3
...
Bube = 10
Dame = 11
König = 12
Ass = 13

Ist das so möglich ???

 

[Firephoenix]

Ich glaube so konkret musst du die Aufgabe garnicht bearbeiten, dort steht ja auch "in Sätzen".
Du kannst also davon ausgehen, dass dein Algorithmus zwei Karten unterscheiden kann.
Auf der Basis könnte man jetzt einen einfachen sortieralgorythmus verwenden, da du immer nur zwei Karten betrachten kannst bietet sich total primitiv der Gnomesort an
Gnomesort ? Wikipedia
Damit müsste man eigentlich einen brauchbaren Pseudo-Algorythmus zusammenschreiben können der einen Stapel aus Karten sortiert, nach dem Motto:

schaue dir die Karte x und Karte y darunter an
wenn Karte y vor Karte x gehört
tausche x mit y
ansonsten ...

irgendwie sowas
Gruß

 

[sk72]

Ich glaube so konkret musst du die Aufgabe garnicht bearbeiten, dort steht ja auch "in Sätzen".

Danke zunächst einmal für die schnelle Antwort.

Die Lösung soll lediglich in einem Pseudocode verfasst werden, das ist richtig.

Gnomesort ist sehr hilfreich, allerdings würde mich interessieren, ob mein Algorithmus auch richtig wäre bzw. ob man das so implementieren könnte ? Ich möchte ja selbst ein wenig rumprobieren.

Gruß

 

[sk72]

Der zweite Teil der Aufgabe ist nämlich folgender:

Beschreiben Sie die “best case” Situation, in der Ihr Algorithmus die wenigsten Ver-
gleichsoperationen zum Sortieren des gesamten Stapels ben¨otigt. Begründen Sie Ihre
Antwort. Schätzen Sie ungef¨ahr ab, wie viele Vergleiche in diesem Fall benötigt werden.
Gehen Sie analog für den “worst case” Fall vor, in dem der Algorithmus maximal viele
Schritte benötigt.

Mit meinem Algorithmus sind es dann in beiden Fällen jeweils 4*13= 52 Operationen. Das ist ja gar nich mal so schlecht !?

 

[Firephoenix]

Also zu der Laufzeit:
Gnomesort ist das primitivste was mir persönlich an sortierverfahren einfallen würde - dafür allerdings leicht zu beschreiben und leicht zu implementieren.
Die Laufzeiten kannst du recht einfach abschätzen (ich hoffe ich konstruiere hier kein falsches Beispiel - daher ohne Gewähr):
Ist das ganze Feld sortiert müsste der Gnom jede Zahl mit jeder anderen tauschen und dabei relativ oft wechseln, dann müsstest du bei den O(n²) landen.
im optimalfall ist das Feld sortiert, dann rennt der Gnom einmal komplett dran vorbei, schaut sich alles an und ist nach dem n. Element am Ende und weiß das er fertig ist : O(n).
Müsst ihr das ganze Teil denn auch in Java-schreiben?
Falls ja kann man sich das sicherlich recht schnell runterschreiben, vorrausgesetzt man implementiert sich erstmal den Kartenstapel.
Stellst du allerdings die Karten mit folgender Zahlenformel auf:
Karte = Farbe + Karte
und wählst für Farbe:
Herz = 000
Kreuz = 100
Pik = 200
Karo = 300
und für Karte:
2 = 2
...
10 = 10
Bube = 11
...

Erhälst du eindeutige Wertebereiche die man numerisch vergleichen kann. Die kleinste Karte wäre die Herz 2 (000 + 2 = 2)
die höchste Karo Ass (300 + 14 = 314).
Die Werte kann man mit etwas Mathe auch leicht wieder zerlegen
Gruß

 

[sk72]

Nein, es geht lediglich darum den Pseudocode zu schreiben.

Ich würde trotzdem gerne meine eigene Idee verfassen, finde das viel spannender und kreativer als einen bestehenden Code zu übernehmen. Daher interessiert mich ja, ob mein Code zu funktionieren würde ? Also ob man meinen Algorithmus in Java implementieren kann ?

Lg

 

[Landei]

Da du genau weißt, wieviel und welche Karten es gibt, weißt du auch genau, wo jede Karte "landen" muss (so wie du beschrieben hast), was das Sortierverfahren trivial macht. Mit etwas gutem Willen könnte man es als vereinfachtes Counting-Sort ansehen.

 

[sk72]

Ich habe mich mit meinem trivial Code nicht zufriedengegeben, daher habe ich mir mal Folgendes einfallen lassen:

Beim nachfolgenden Algorithmus wird davon ausgegangen, dass jede Karte einen Wert besitzt ( z.B. „Karo Ass“ den höchsten Wert, „Pik 2“ hat einen höheren Wert als „Herz König“ oder „Kreuz 10“ hat einen höheren Wert als „Kreuz 9“ )


1. Vergleiche den Wert zweier aufeinanderfolgender Karten ( 1. und 2. Karte, 3. und 4. Karte, 5. und 6. Karte usw. )

tausche die Position, falls die Karten in ungeordneter Reihenfolge nebeneinander liegen
behalte die Position bei, falls das Paar geordnet nebeneinander liegt

2. Vergleiche den Wert den zweier aufeinanderfolgender Karten ( 2. und 3. Karte, 4 und 5. Karte, 6. und 7. Karte, d.h. die erste und letzte Karte werden bei diesem Vorgang ausgelassen )

tausche die Position, falls die Karten in ungeordneter Reihenfolge nebeneinander liegen
behalte die Position bei, falls das Paar geordnet nebeneinander liegt

1. Vergleiche den Wert zweier aufeinanderfolgender Karten ( 1. und 2. Karte, 3. und 4. Karte, 5. und 6. Karte usw. )

tausche die Position, falls die Karten in ungeordneter Reihenfolge nebeneinander liegen
behalte die Position bei, falls das Paar geordnet nebeneinander liegt

2. Vergleiche den Wert den zweier aufeinanderfolgender Karten ( 2. und 3. Karte, 4 und 5. Karte, 6. und 7. Karte, d.h. die erste und letzte Karte werden bei diesem Vorgang ausgelassen )

tausche die Position, falls die Karten in ungeordneter Reihenfolge nebeneinander liegen
behalte die Position bei, falls das Paar geordnet nebeneinander liegt


Wiederhole abwechselnd 1. und 2. bis die Karten in geordneter Reihenfolge nebeneinanderliegen, d.h. bis bis keine Karten mehr getauscht werden


Zwecks Übersichtlichkeit als pdf: blaa.pdf (41,00 KB) - uploaded.to

 

[sk72]

Ich bin euren ganzen Tipps natürlich sehr, sehr danksam und darauf basiert auch mein Code, allerdings möchte ich keine Idee 1:1 kopieren, sondern einen "eigenen" Algorithmus entwerfen !

 

[sk72]

Noch ein weiteres PDF, dass meinen Algorithmus bildhaft erklären soll: blaa2.pdf (19,60 KB) - uploaded.to

 

[Manu247327]

sag mal, du studierst nich zufällig wifo an der uni mannheim? xD
sitz nämlich selbst an der aufgabe