Profil von Aconcagua

17.06.2016, 19:41

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

Guten Tag, ich habe gerade ein Sortieralgorithmus für ein Array geschrieben. Ich hielt es für Sinnvoll, dass man als erstes das Array nach den 10er Zahlen sortiert: Alt: 4, 19, 1, 90, 53, 28, 20,... Neu: 4, 1, 19, 28, 20, 53, 90,... Mein Code dafür:

for (int i=0; i<unserArray.length; i++){
        if(String.valueOf(unserArray[i]).length() != 1){
            zehnerstelle = Integer.parseInt(String.valueOf(unserArray[i]).substring(0, String.valueOf(unserArray[i]).length()-1));
        }
        else{
            zehnerstelle = 0;
        }
        sortedNumbers[zehnerstelle][insertPos[zehnerstelle]] = unserArray[i];
        insertPos[zehnerstelle]++;
    }
    
    for (int i=0; i<sortedNumbers.length; i++){
        for (int j=0; j<sortedNumbers[i].length && sortedNumbers[i][j]!=0; j++){
            unserArray[insertPosUnserArray]=sortedNumbers[i][j];
            insertPosUnserArray++;
        }
    }

Wie ihr bestimmt schon seht, bin ich hier noch nicht fertig. So muss das Array quasi noch nach den 1er Stellen sortiert werden ohne, dass die 10er Stellen getauscht werden müssen. Gibt es da eine möglichst effiziente Möglichkeit?

...zum Beitrag

Antwort

von Aconcagua

17.06.2016, 23:09

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...