[GO] Sortieren Sie schnell ein Array in Python 3

Einführung

Frohes Neues Jahr 2020, alle zusammen. Ich heiße ryuichi69.
Ich habe diesen Satz heute geschrieben, nachdem ich die Ausgabe und Erklärung des Algorithmus geübt hatte. Um ehrlich zu sein, ist es schwierig, leicht verständlich zu schreiben. Wenn Teile der Erklärung schwer zu verstehen sind oder wenn Anforderungen fehlen, wenden Sie sich bitte an uns.

Schnelle Sortierung

Übersicht

Sortieren bedeutet zunächst, die Elemente eines Arrays in aufsteigender oder absteigender Reihenfolge zu sortieren. Es gibt viele Arten von

-Sortiermethoden, aber die schnelle Sortierung basiert auf dem Referenzwert des -Arrays und wird dann durch Unterteilen in größere und kleinere Arrays sortiert. Es ist eine Methode, um zu gehen.

Beispiel für eine schnelle Sortierung

Zum Beispiel gibt es ein Array a = [5,6,3,1,8], und Sie sollten dies schnell in aufsteigender Reihenfolge sortieren. Darüber hinaus wird der Medianwert im Array als Referenzwert verwendet.

Hier beträgt der Medianwert der Elemente des Arrays a 3. Mit dieser 3 als Grenze werden die Elemente, die kleiner als 3 sind, in zwei Hälften geteilt, z. B. blau unten und die Elemente größer als 3 unten gelb. Darüber hinaus wird das Array, wie in der zweiten Unterteilung in der folgenden Abbildung gezeigt, rekursiv in zwei Hälften geteilt, und die Wiederholung wird gestoppt, wenn die Anzahl der Elemente im Array eins wird. Zum Abschluss wird es in ein Array integriert.

sort.png

Hier ist eine Zusammenfassung des Implementierungsverfahrens.

Implementierungsverfahren
  1. Finden Sie den Median m (Referenzwert) des Elements e in Array a [i].
  2. Wenn die Anzahl der Elemente im Array nach der Division eins wird, schreiben Sie einen Prozess, um die Wiederholung zu stoppen (Rekursionsstoppbedingung).
  3. Für jedes Elementelement des Arrays. Wenn a [i] m, speichern Sie das Element im Array rechts.
  4. Die obigen 1 und 2 werden rekursiv für das Array links und das Array rechts ausgeführt.

    Beispiel Sei

    n eine natürliche Zahl und i eine ganze Zahl, die 0 ≤ i ≤ (n-1) erfüllt. Verwenden Sie zu diesem Zeitpunkt die schnelle Sortierung, um das Array a [i] mit n Elementen in aufsteigender Reihenfolge zu sortieren.

    Einschränkungen
    1. 1≦n≦10
    2. 1≦a[i]≦10
    Eingabe

    a = [7,3,10,5,9,1,6,4,8,2]

    Ausgabe

    [1,2,3,4,5,6,7,8,9,10]

    Programm

    Der Quellcode lautet @ suecharos " Sortieralgorithmus und Implementierung in Python --Qiita Es basiert auf der schnellen Art von ". Ich wusste nicht, wie ich das Array in zwei Teile teilen und sortieren sollte, also entschied ich mich dafür.

    quickSort.py

    
import os
import statistics

def quickSort(arr):

    #Ein Array von Elementen, die kleiner als der Median des Arrays sind
    left = []

    #Ein Array von Elementen, die größer als der Median des Arrays sind
    right = []

    #Wiederholungsstoppbedingung
    #Stoppen Sie, wenn die Anzahl der Elemente nach rekursivem Teilen des Arrays 1 oder weniger wird
    if len(arr) <= 1:
        return arr

    #Medianwert des Arrays(Median)Bekommen
    median = int(statistics.median(arr))

    #Eine Variable zum Zählen der Anzahl der in einem Array enthaltenen Medianwerte
    medianFlg = 0

    for element in arr:
        #Elemente des Arrays(element)Ist kleiner als der Median
        #Speichern Sie den Wert im Array links
        if element < median:
            left.append(element)
        #Elemente des Arrays(element)Ist größer als der Median
        #Speichern Sie die Werte im Array rechts
        elif element > median:
            right.append(element)
        else:
        #Wenn element der Medianwert des Arrays ist
        #Flags für die Anzahl der Medianwerte, die zum Rückgabewert hinzugefügt wurden+1 Weiter
            medianFlg += 1

    #Wenn Sie sehen möchten, wie das Array aufgeteilt ist,
    #Es ist gut, zu diesem Zeitpunkt mit dem Druck zu prüfen
    # print(left)
    # print(right)

    #Führen Sie eine Rekursion für jedes Array links und Array rechts durch
    #Teilen Sie das Array in kleinere Arrays
    left = quickSort(left)
    right = quickSort(right)

    #Array links, Median[median], Gibt eine Verkettung des Array-Rechts zurück
    return left + [median] * medianFlg + right

#zum Test
if __name__ == "__main__":

    print(quickSort([7,3,10,5,9,1,6,4,8,2]))

    Recommended Posts