sortieren

[Paddy.]

Ich hab eine Array von Objekten (die compareTo implementieren)
Scheinbar gibts die Collections.sort in der j2me nicht;(
Also hatte besser eine art bubble-Sort was auch gut funktioniertte bis meine Objekt Anzahl zu groß wurde. Und die anzeige der Objekte ins nichts verläuft bzw. erst nach 5min fertig ist*g* bischen dumm.

Hat jmd eine Möglichkeit bzw. Vorschläge welcher Sortier-Algorithmus zeitmäßig effizient läuft.???:L

 

[madboy]

Sortieralgorithmen gibt's ne ganze Menge. Frage einfach mal Wikipedia danach.
Der Einfachheit halber könntest du aber auch die entsprechende(n) Methode(n) aus Collections kopieren. Dabei aber die Lizenz beachten ;-)

 

[Paddy.]

ja aber was ist den speicher und geschwindkeitsoptimal für ein mobiltelefon ???:L

Programmieren könnte ich die meisten selbst nur war ich zu faul bisher und dachte das macht bei den 100 net soviel aus :rtfm:

 

[XHelp]

Halbwissen: kannst du dir nicht RecordStrore basteln? Dazu kannst du auch ein Comparator basteln und er sortiert es automatisch. Ich denke das Verfahren wurde da passend umgesetzt.

 

[Paddy.]

ich kann mir eigentlich nicht vorstellen das die Objekte serielliesieren ins Dateisystem schreiben, sortieren, auslesen schneller sein soll als nur sortieren?

 

[ARadauer]

ja aber was ist den speicher und geschwindkeitsoptimal für ein mobiltelefon ???:L

Programmieren könnte ich die meisten selbst nur war ich zu faul bisher und dachte das macht bei den 100 net soviel aus :rtfm:

Mhn um wie viele Elemente geht es den?
Die API verwendet normalerweise merge sort... das würd ich einfach mal ausprobieren...

 

[SlaterB]

Quellcode von Collections.sort() kopieren?

 

[Landei]

Hast du bei J2ME TreeSet oder TreeMap? Damit könntest du auch sortieren.

 

[Paddy.]

normale LinkedList gibts nicht? das wäre toll dann könnte man sinnvoll bei der Erstellung der Liste sortieren.

 

[Landei]

LinkedList wäre grauenhaft, besser als O(n²) ginge nicht.

 

[Paddy.]

ja meine Liste wird einmalig bei Programmstart aufgebaut, dann sortiert und verwendet. Spätere hinzufügen und daher auch sortieren ist nicht nötig.
:rtfm: Dachte wenn ich die beim aufbau da einfüge wo sie hin gehören ???:L
Dann müsste ich worst Case die Liste Komplett durchlaufen, die aber nur am ende n ist und voher kleiner. Also beim ersten mal 1 dann 2,....(n-1), n das ist doch schneller als n²

 

[Landei]

Ist trotzdem proportional zu n²

 

[Paddy.]

*Idee verwirft*
War das ne Frage obs TreeSet/TreeMaps gibt?
Ich hab irgendwie nur Hashtable in java-util gefunden.

 

[Landei]

Schade, hätte ja sein können...

 

[Gelöschtes Mitglied 5909]

wie wärs denn mit Arrays.sort() wenn du eh schon ein Arrays hast?

 

[Paddy.]

???:L Gibts auch net:rtfm:

 

[andiv]

Bevor du jetzt ewig drüber nachdenkst wie du sortieren kannst, würd ich an deiner Stelle entweder eine Implementation von Collections.sort() kopieren oder kurz ein MergeSort, QuickSort oder HeapSort implementieren. Die haben alle im average-case O(n*log(n)) und sind auch nicht sonderlich schwer zu programmieren.

 

[ThreadPool]

normale LinkedList gibts nicht? das wäre toll dann könnte man sinnvoll bei der Erstellung der Liste sortieren.

Jupp, funktioniert. Du verwendest dann zum Einfügen und Finden die Binäre Suche, das funktioniert, weil die Liste ja immer sortiert sein soll. Zur Frage der Speichereffizienz da würde man denke ich die Inplace-Variante von Mergesort nehmen wenn es denn um ein "sortieren on demand" geht.

 

[Landei]

Die binäre Suche wäre im Endeffekt langsamer als eine lineare, weil bei einer LinkedList beim indizierten Zugriff nicht wie bei einer ArrayList direkt zum gewünschten Element gesprungen werden kann, sondern von vorn gestartet wird.

 

[ThreadPool]

Hm, da hatte ich wohl zu sehr an eine ArrayList gedacht. Wenn er die nimmt sollte es wieder gehen.
Alternativ kann er sich auch eine Skipliste bauen die natürlich wieder mehr Speicher verbraucht.

 

[Landei]

Es schwirren doch jede Menge Implementierungen durchs Netz. Hier z.B. ein in-place Mergesort: MergeSortAlgorithm.java