Proxmap-Algorithmus

Lange Zeit galten Sortieralgorithmen wie etwa Quicksort mit der Komplexität O(n * log(n)) als die bestmöglichen Sortierverfahren. Es ist sogar möglich zu beweisen, dass man für diese Art der Sortieralgorithmen die Komplexität nicht weiter reduzieren kann. Daher wird es hier Zeit für einen neuen Ansatz:

Beobachtet man einen Menschen, wie er Spielkarten sortiert, fällt auf, dass er die Karten bereits intuituv an die richtige Stelle legt, ohne vorher alle anderen Karten geprüft zu haben. So wandert das Ass ganz nach rechts und die zwei ganz nach links. Auf diese Weise muss ein Kartenspieler jede Karte meist nur ein einziges Mal anfassen ehe sie auf der richtigen Position liegt:

Genau das gleiche wollen wir auch mit dem Proxmap-Algorithmus durchführen. Wir verschaffen uns als erstes einen Überblick, über die Verteilung der zu Sortierungen Werte und raten anschließend die Position der einzelnen Elemente. Haben wir uns dabei einmal vertan, so müssen wir nur die betroffenen Elemente umsortieren:

Da der Rechner keine Karten kennt werden wir den Buben die 11, der Dame die 12, dem König die 13 und dem Ass die 14 zuordnen.

In diesem Beispiel haben wir also die 14, 12, 4, 13, 2 und 6 und möchten diese sortieren. Hätten wir 14 Ablageplätze wäre die Aufgabe trivial:

Die Karten nacheinander auf ihre jeweilige Position legen und anschließend leere Felder entfernen:

Klar können wir uns bei Spielkarten viel Platz nehmen. Wollen wir aber etwa aus drei Spielkartensets nur 4 Karten ziehen und diese ordnen, würde es auf dem Tisch ziemlich eng werden.

Nehemen wir in diesem Beispiel einfach 6 Ablagemöglichkeiten für die 4 Karten und legen jede Karte an den Platz, wo sie in etwa hinkommen sollte. Man könnte etwa Kartenwert / maximaler Kartenwert rechnen, um die Position in Prozent zu erhalten. 7 / 14 würde folglich ergeben, dass die 7 bei 0,5 also ziemlich in der Mitte liegen müsste. Rundet man das Ergebnis der Berechnung Kartenwert / maximaler Kartenwert * Anzahl Ablagemöglichkeiten auf eine ganze Zahl, erhält man eine genaue Position für die Karte.

Für die 10 rechnen wir 10 / 14 * 6 ≈ 4:

Für die 3 rechnen wir 3 / 14 * 6 ≈ 1:

Für die 9 rechnen wir 9 / 14 * 6 ≈ 4. Jetzt haben wir das Problem, dass das Feld schon besetzt ist. Also prüfen wir, ob die Karte auf dem Feld größer ist. Ist das der Fall, so tauschen wir beide Karten gegeneinander:

Noch haben wir das gleiche Problem wie eben. Aber jetzt kann ich anstelle auf Positon 4 zu gehen eins weiter rutschen und Position 5 probieren:

Da hier Platz war, konnte ich die Karte ablegen. Wäre dem nicht so hätten wir einfach wieder begonnen zu Prüfen, ob wir die Karten tauschen müssen und wären dann noch einen Platz nach rechts gerutscht.

w> Der Algorithmus funktioniert natürlich nur, solange man nach rechts rutschen kann. Ist das Ende erreicht würde man sich in die entgegengesetzt Richtung bewegen.

Schlussendlich legen wir das Ass bei 14 / 14 * 6 = 6 ab:

Jetzt noch die Lücken entfernen, und wir haben die Karten sortiert:

Sicher ist dir aufgefallen, dass wir weniger umstecken müssen, wenn wir mehr Ablageplätze haben. In der Praxis hat sich bewährt, dasss nur 75% der Ablageplätze belegt werden sollen.

Bisher sind wir immer von einer Gleichverteilung ausgegangen. Das ist natürlich nicht immer so. Etwa beim Sortieren eines Adressbuches oder wenn der Körpergröße von SchülerInnen. In diesem Fall würde man das bei der Analyse der Menge eine andere Berechnung zur Bestimmung der Position verwenden und an Häufungspunkten mehr Ablagemöglichkeiten einplanen.

Als Programm könnte das etwa wie folgt aussehen:

x
  
  

  

  

    

      

      

      
//dataset - array with unsorted list
    
    

      
//targetdataset - array for sorted list
    
    

      
​
    
    

      
//fill target dataset
    
    

      
for (i = 0; i < dataset.length; i++) {
    
    
    //quess position: calc percent of max value * positions
    

      
    var pos = Math.round(dataset[i] / (dataset.length * 2) * (targetdataset.length - 1));
    
    

      
    var hand = dataset[i];
    
    

      
    var plus = true;
    
    

      
    while (targetdataset[pos] != null) {
    
    

      
        if (plus) {
    
    

      
            if (hand < targetdataset[pos]) {
    
    

      
                //swap hand and target if hand is smaller then target
    
    

      
                temp = hand;
    
    

      
                hand = targetdataset[pos];
    
    

      
                targetdataset[pos] = temp;
    
    

      
            }
    
    

      
            pos++;
    
    

      
        if (pos == targetdataset.length - 1) plus = false; //change direction if on end
    
    

      
        }
    
    

      
        else {
    
    

      
            if (hand > targetdataset[pos]) {
    
    

      
                //wap hand and target if hand is smaller then target
    
    
                temp = hand;
    
                hand = targetdataset[pos];
    
                targetdataset[pos] = temp;
    
            }
    

      
            pos--;
    
    

      
        }
    
    

      
    }
    
    

      
    //empty feld: set value
    
    
    targetdataset[pos] = hand;
    

      
}
    
    

      
​
    
    
//remove empty fields
    

      
for (i = 1; i < targetdataset.length; i++) {
    
    

      
    if (targetdataset[i].num != null && i>0) {
    
    

      
        var exit = false;
    
    

      
        while (targetdataset[i-1].num == null && !exit) {
    
    

      
        temp = targetdataset[i];
    
    
        targetdataset[i] = targetdataset[i-1];
    
        targetdataset[i-1] = temp;
    
​
    

      
        if (i==1) {
    
    

      
            exit=true;
    
    
        } 
    
        else {
    

      
            i--;
    
    
        } 
    

      
    }   
    
    

      
}