Map Sort

Map Sort ist ein in Linearzeit ablaufender Sortieralgorithmus.

Idee

• Es wird eine größere Zwischenliste erstellt
  • Bei Gleichverteilung der Elemente ist das Array -mal so groß
• Der Wertebereich wird berechnet
• Die Elemente werden in der Zwischenliste an ihre ungefähre Position im Wertebereich gesetzt Beispiel: Bei einem Wertebereich von 0-8 ist die Zwischenliste 10 Elemente groß. Die 4 ist bei 50% des Wertebereiches, wird also bei 50% von 10, also an Position 5 eingesetzt.
• Kommt es zu Kollisionen, werden Elemente nach links oder rechts verschoben.

Laufzeit

Map Sort hat eine Laufzeit von , falls die Eingabewerte gleichverteilt sind

Implementierung

def mapSort(inputArray, arrayLength, compressionFactor)
    binSize = arrayLength * compressionFactor
    minValue = min(inputArray)
    maxValue = max(inputArray)
 
    Erstelle bins[binSize] und initialisiere alle Werte mit -1
 
    binInterval = (maxValue - minValue) / (binSize - 1)
 
    for value in inputArray
        targetBin = (value - minValue) / binInterval
        insertToLeft = False
 
        if bins[targetBin] != -1 and value <= bins[targetBin]
            insertToLeft = True
 
        while bins[targetBin] != -1
            if insertToLeft
                if value > bins[targetBin]
                    Tausche bins[targetBin] mit value
                if targetBin > 0
                    targetBin = targetBin - 1
                else
                    insertToLeft = False
            else
                if value <= bins[targetBin]
                    Tausche bins[targetBin] mit value
                if targetBin < binSize - 1
                    targetBin = targetBin + 1
                else
                    insertToLeft = True
 
        bins[targetBin] = value
 
    index = 0
    for i in range(0, binSize - 1)
        if bins[i] != -1
            inputArray[index] = bins[i]
            index = index + 1