median der drei Werte-Strategie

Einer Umsetzung der Median der Drei, die ich gefunden habe funktioniert gut in meiner schnellen sortiert.

(Python)
# Get the median of three of the array, changing the array as you do.
# arr = Data Structure (List)
# left = Left most index into list to find MOT on.
# right = Right most index into list to find MOT on

def MedianOfThree(arr, left, right):
    mid = (left + right)/2
    if arr[right] < arr[left]:
        Swap(arr, left, right)        
    if arr[mid] < arr[left]:
        Swap(arr, mid, left)
    if arr[right] < arr[mid]:
        Swap(arr, right, mid)
    return mid

# Generic Swap for manipulating list data.
def Swap(arr, left, right):
    temp = arr[left]
    arr[left] = arr[right]
    arr[right] = temp    

InformationsquelleAutor der Antwort rahvin_t

Gemeinsam/Vanille quicksort wählt als Pivotelement das äußerste Rechte element. Dies hat zur Folge, dass es Exponate der pathologischen Leistung O(N2) für eine Reihe von Fällen. Insbesondere die sortiert und Umgekehrt sortierten Sammlungen. In beiden Fällen ist das Rechte element die schlechteste element zu wählen als Pivotelement. Der pivot ist ideal dachte mir in der Mitte von der Partitionierung. Die Partitionierung soll so teilen Sie die Daten mit der pivot in zwei Abschnitte, einen niedrigen und einen hohen Abschnitt. Niedrige Abschnitt niedriger als der Drehpunkt, den hohen Abschnitt höher.

Median-von-drei pivot-Auswahl:

• wählen Sie ganz Links, mittlere und Rechte element
• bestellen Sie die linke partition, pivot und die richtige partition. Verwenden Sie die pivot in der gleichen Weise wie regelmäßige quicksort.

Den häufigsten Pathologien O(N2) sortiert /rückwärts sortierte Eingaben werden gemildert. Ist es immer noch einfach zu erstellen pathologischen Eingänge median-von-drei. Aber es ist ein konstruiertes und schädliche Verwendung. Nicht einen natürlichen Bestellung.

Randomisierte pivot:

• wählen Sie ein zufälliges pivot. Verwenden Sie diese als regelmäßige pivot-element.

Wenn zufällige, das nicht eine pathologische O(N2) Verhalten. Die zufälligen pivot ist in der Regel sehr wahrscheinlich rechenintensive für eine generische Art und als solche unerwünscht. Und wenn es nicht zufällig (d.h. srand(0); rand(), berechenbar und anfällig für die gleichen O(N2) auszunutzen, wie oben beschrieben.

Beachten Sie, dass die zufälligen pivot - nicht profitieren Sie von der Auswahl mehr als ein element. Vor allem, weil die Wirkung der median ist bereits eine intrinsische, und ein zufälliger Wert ist mehr rechenintensive als auch die Bestellung von zwei Elementen.

InformationsquelleAutor der Antwort Captain Giraffe

Können wir verstehen, die Strategie der median der drei durch ein Beispiel, angenommen wir haben ein array:

[8, 2, 4, 5, 7, 1]

Also die am weitesten Links stehende element ist 8und ganz Rechte element ist 1. Das mittlere element ist 4da für jede array mit der Länge 2kwählen wir die kth-element.

Und dann Sortieren wir diese drei Elemente in aufsteigender Reihenfolge oder absteigender Reihenfolge, die gibt uns:

[1, 4, 8]

So, der median ist 4. Und wir verwenden 4 als unser pivot.

Auf die Umsetzung Seite haben, können wir:

//javascript
function findMedianOfThree(array) {
    var len = array.length;
    var firstElement = array[0];          
    var lastElement = array[len-1];
    var middleIndex = len%2 ? (len-1)/2 : (len/2)-1;
    var middleElement = array[middleIndex];
    var sortedArray = [firstElement, lastElement, middleElement].sort(function(a, b) {
        return a < b; //descending order in this case
    });
    return sortedArray[1];
}

Einen anderen Weg, um es zu implementieren ist inspiriert von @kwrl, und ich möchte erklären, es ein bisschen klarer:

    //javascript
    function findMedian(first, second, third) {
        if ((second - first) * (third - first) < 0) { 
            return first;
        }else if ((first - second) * (third - second) < 0) {
            return second;
        }else if ((first - third)*(second - third) < 0) {
            return third;
        }
    }
    function findMedianOfThree(array) {
        var len = array.length;
        var firstElement = array[0];          
        var lastElement = array[len-1];
        var middleIndex = len%2 ? (len-1)/2 : (len/2)-1;
        var middleElement = array[middleIndex];
        var medianValue = findMedian(firstElement, lastElement, middleElement);
        return medianValue;
    }

Betrachte die Funktion findMedianerste element zurückgeben, nur wenn second Element > first Element > third Element und third Element > first Element > second Elementund in beiden Fällen: (second - first) * (third - first) < 0 die gleiche Argumentation anwenden, um die verbleibenden zwei Fällen.

Den Kopf, mit der zweiten Implementierung ist, dass Sie könnten haben eine bessere Laufzeit.

InformationsquelleAutor der Antwort Leonard Ge