# sortieren



## Paddy. (13. Dez 2010)

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 (13. Dez 2010)

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. (13. Dez 2010)

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 (13. Dez 2010)

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. (14. Dez 2010)

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


----------



## ARadauer (14. Dez 2010)

Paddy. hat gesagt.:


> 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 (14. Dez 2010)

Quellcode von Collections.sort() kopieren?


----------



## Landei (14. Dez 2010)

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


----------



## Paddy. (14. Dez 2010)

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


----------



## Landei (14. Dez 2010)

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


----------



## Paddy. (14. Dez 2010)

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 (14. Dez 2010)

Ist trotzdem proportional zu n²


----------



## Paddy. (14. Dez 2010)

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


----------



## Landei (14. Dez 2010)

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


----------



## Gelöschtes Mitglied 5909 (14. Dez 2010)

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


----------



## Paddy. (14. Dez 2010)

???:L Gibts auch net:rtfm:


----------



## andiv (15. Dez 2010)

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 (15. Dez 2010)

Paddy. hat gesagt.:


> 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 (15. Dez 2010)

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 (15. Dez 2010)

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 (15. Dez 2010)

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


----------

