Wie kann man ein Array in Java am effizientesten sortieren, wenn man weiß, dass die 10er Stellen schon richtig sind?

... komplette Frage anzeigen

4 Antworten

Wieso zum Henker sortierst du nach Zehner/Einer (evt. sogar Hunderter)??

Letzten endes ergibt sich hier doch ein "nach größe Sortiertes" Array, wieso soriterst du es nicht direkt nach Größe und benutzt somit jede Zahl als Ganzes??

Solltest du es aber dennoch in deinem Weg machen müssen, kannst du mich das auch wissen lassen dann helfe ich dir.

MFG xGlumi

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von OneZeroByte
17.06.2016, 19:56

Einfach, weil ich gerne etwas eigenes schreiben wollte und nicht irgend ein schon existierendes Verfahren nehmen wollte. Außerdem ist dieses Verfahren bis jetzt viel effizienter als alles andere, was ich probiert habe (von der Anzahl der Vergleiche her)

0

Ganz vorneweg - konvertieren in String, substring, und Konvertierung zurück? Das ist absolut katastrophal... Ich nehme mal an, es ist ein int- oder long-Array. Dann bekommt man die Zehner durch eine simple Division durch 10. Eventuelle Nachkommastellen werden dabei einfach fallen gelassen (7/10 ergibt ganz banal 0, 10/10 und 12/10 alle beide 1 (sodass 10/10 == 12/10 gilt...).

Es handelt sich bei der Vorsortierung offenbar um eine Variante des Bucketsort. Gibt es denn irgendeine Beschränkung, wie groß die Zahlen in unserArray sein können? Ansonsten müsste das sortedNumbers-Array ja fast 215 Mio Einträge haben (int; keine negativen Zahlen berücksichtigt!) bzw. würde definitiv den Arbeitsspeicher sprengen (long). Was ist mit negativen Zahlen? ArrayIndexOutOfBoundsException lässt grüßen...

Sind Duplikate bei den Werten erlaubt? Dann müsste gelten: sortedArray = new int[(1 << 31) / 10) + 1][unserArray.length] (wiederum ohne negative Werte zu berücksichtigen, ansonsten bräuchten wir (int)(((long)1 << 32) / 10) + 1!). Es könnte ja sein, dass das unserArray z. B. einfach nur jeweils 1000 mal die Zahlen 2010 und 2012 enthält....

Wenn es also keine sinnvollen Beschränkungen der Einzelwerte gibt, liegt die gewählte Datenstruktur irgendwo zwischen äußerst ungünstig bis komplett ungeeignet. Dann ist es sicherlich effizienter, gleich das ganze unserArray mit java.util.Arrays.sort zu sortieren ( https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(int[]) ).

Wenn es aber geeignete Begrenzungen gibt, dann komme ich gleich nochmal auf vorherigen Abschnitt zurück: Lasse die einzelnen Unter-Arrays in sortedNumbers jeweils von java.util.Arrays.sort sortieren...

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von OneZeroByte
23.06.2016, 09:11

Ja, in der Tat gibt es eine Begrenzung.

1. unserArray hat int Werte von 1-100

2. Die Werte können mehrfach vorkommen

3. unserArray ist 50 lang

Aber was bedeutet in: sortedArray = new int[(1 << 31) / 10) + 1][unserArray.length] das: [(1 << 31) / 10) + 1] (Speziell das <<?

0

Am besten du informierst dich mal über den Algorithmus RadixSort. Der funktioniert sehr ähnlich zu deinem Ansatz.

Antwort bewerten Vielen Dank für Deine Bewertung

Java benutzt TimSort, was SEHR effizient arbeitet, wenn bestimmte Teile schon vorsortiert sind:

https://de.wikipedia.org/wiki/Timsort

Wenn du also bereits die 10er Stellen sortiert hast, und dann Arrays.sort() darüber laufen lässt, sollte es sehr effizient sein.

Allerdings wird es garantiert effizienter, wenn du von Anfang an auf Javas Sortieralgorithmen vertraust.

Das, was du da tust, würde ich sein lassen. Es sei denn, es handelt sich nur um eine Übung. In diesem Falle beachte bitte unbedingt die Antwort von Aconcagua!

Naja, viel Spaß noch beim Lernen! ;)

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?