Frage zu Bucketsort

jw.
Erstie
Erstie
Beiträge: 12
Registriert: 20. Apr 2013 11:54

Frage zu Bucketsort

Beitrag von jw. »

Hi ich habe mal eine Frage zu BucketSort:

Man soll ja in A alle Strings der Länge entsprechend speichern, also zB in A[1] alle Inputstrings mit nur einem Buchstaben. Wie ist das denn gemeint? Bzw. wie kann ich in ein ArrayFeld mehrere Strings schreiben, ohne sie zusammenzuhängen?

im WIKI steht:
An array A with index range [1,....,N] and multisets of strings as components.

Kann mir das vielleicht mal jemand erklären? Vielen Dank schonmal.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Frage zu Bucketsort

Beitrag von JannikV »

Hey, der springende Punkt ist ... and multisets of strings as components. Das Array enthält Mengen (genauer Multisets, diese lassen auch Duplikate zu). In diese Mengen kannst du dann ja problemlos mehrere String einfügen.

VG

jw.
Erstie
Erstie
Beiträge: 12
Registriert: 20. Apr 2013 11:54

Re: Frage zu Bucketsort

Beitrag von jw. »

Ok vielen Dank schonmal :-). Das Problem ist das mir der Begriff multiset nicht geläufig war bzw. das ich nicht weiss, was in Java damit konkret gemeint ist. Habe jetzt über google rausgefunden das es sowas für C++ gibt, aber nicht für Java (oder doch?).

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Frage zu Bucketsort

Beitrag von JannikV »

Ah ok.

Ein Set, also eine Menge ist eine Datenstruktur die ungeordnet einen Haufen Elemente speichern kann. Duplikate können darin nicht enthalten sein. Intuitiv deckt sich das gut mit den aus der Mathematik bekannten Mengen. In Java gibt es da beispielsweise die Klasse HashSet, die intern aus Performance Gründen mit Hashwerten arbeitet.

Ein Multiset ist praktisch das gleiche, nur dass hier Duplikate erlaubt sind. In der Tat gibt es keine Entsprechung in der Standard Java API.
Das ist aber auch nicht wichtig, denn die Algorithmen sollen hier ja abstrakt betrachtet werden und nicht in einer konkreten Implementierung.
Man könnte jedoch überlegen selbst eine Java Klasse zu schreiben, die ein Multiset realisiert oder sich nach bereits existierenden Bibliotheken umsehen.

VG

jw.
Erstie
Erstie
Beiträge: 12
Registriert: 20. Apr 2013 11:54

Re: Frage zu Bucketsort

Beitrag von jw. »

Danke, jetzt ist mir klar wie das gemeint ist, war zu Java-fixiert :D

Lars Gußmann
Neuling
Neuling
Beiträge: 2
Registriert: 23. Mai 2013 17:40

Re: Frage zu Bucketsort

Beitrag von Lars Gußmann »

Ich hätte noch eine Frage bezüglich des sets.
Hier wurde nun einmal geschrieben es darf Duplikate enthalten und einmal es darf keine enthalten.
Für die Aufgabenstellung würde es Sinn ergeben, wenn es Duplikate enthalten darf.

Darf ich also davon ausgehen, dass das hier auch der Fall ist, denn im Beispiel das zu bearbeiten ist, ist "Bier" doppelt enthalten.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Frage zu Bucketsort

Beitrag von JannikV »

Hi, sets enthalten keine Duplikate, multisets können das.
Bei bucketsort werden multisets eingesetzt.

Antworten

Zurück zu „Archiv“