Sortieralgorithmus und Implementierung in Python

Einführung

Ich habe einige Sortieralgorithmen zusammengefasst.

Ich habe jeden Punkt, ein Implementierungsbeispiel in Python und jede Geschwindigkeitsmessung beschrieben.

Ich habe es implementiert, ohne so viele integrierte Funktionen wie möglich zu verwenden, daher ist es nicht sehr schnell, aber ich wollte etwas schneller machen als sort () und sorted ().

Zu handhabender Sortieralgorithmus

Der zu behandelnde Sortieralgorithmus ist

• Blasensortierung
• Sortierung auswählen
• Sort einfügen --Zusammenführen, sortieren --Schnelle Sorte
• Zählsortierung

Andere bekannte Sortieralgorithmen sind Heap-Sortierung, Shell-Sortierung und Radix-Sortierung, aber diesmal habe ich sie vergessen. Ich möchte es eines Tages hinzufügen.

Die Heap-Sortierung ist mit dem Heapq-Modul von Python recht einfach zu implementieren, aber es fühlt sich anders an als sort () ...

Stabilität bedeutet, dass beim Sortieren von Daten wie [1-b, 2-a, 1-a, 2-b] unter Verwendung von Zahlen als Schlüssel die Reihenfolge vor dem Sortieren gespeichert wird und [1-b, Wir erkennen, dass so etwas wie 1-a, 2-a, 2-b] als stabil definiert ist.

Jeder Punkt und jede Implementierung

Blasensorte

--Vergleichen und tauschen Sie die Größe jeder Seite aus und tun Sie dies, bis keine Änderungen mehr erforderlich sind.

• Einfach und leicht zu verstehen.

bubble_sort.py

def bubble_sort(arr):
    change = True
    while change:
        change = False
        for i in range(len(arr) - 1):
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]
                change = True
    return arr

Selektive Sortierung

--Wählen Sie das Minimum oder Maximum im Array und verschieben Sie es bis zum Ende.

• Einfach und leicht zu verstehen.

Ich habe das Gefühl, ich kann min () verwenden ...

Um die Speichernutzung auf $ O (1) $ zu reduzieren, wird sie durch Ersetzen implementiert, anstatt sie in eine neue Liste aufzunehmen.

sellect_sort.py

def sellect_sort(arr):
    for ind, ele in enumerate(arr):
        min_ind = min(range(ind, len(arr)), key=arr.__getitem__)
        arr[ind], arr[min_ind] = arr[min_ind], ele
    return arr

Sortierung einfügen

• In der Reihenfolge von links in den entsprechenden Teil des ausgerichteten Arrays einfügen. --Wenn Sie nach einem Platz zum Einfügen suchen, können Sie die Suche mithilfe einer 2-minütigen Suche beschleunigen.
• Im Vergleich zum Zusammenführen von Sortieren und schnellem Sortieren hängt dies nicht vom Status der Daten ab.
• Stark gegen fast sortierte Arrays und relativ kleine Arrays.
• Einfach und leicht zu verstehen.

Wenn Sie die 2-Minuten-Suche nicht verwenden

insert_sort.py

def insert_sort(arr):
    for i in range(1, len(arr)):
        j = i - 1
        ele = arr[i]
        while arr[j] > ele and j >= 0:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = ele
    return arr

Bei Verwendung der 2-Minuten-Suche

insert_sort_bin.py

import sys
sys.setrecursionlimit(10 ** 7)

def binary_search(arr, low, hig, ele):
    if low == hig:
        if arr[low] > ele:
            return low
        else:
            return low + 1
    elif low > hig:
        return low
    
    mid = (low + hig) // 2
    if arr[mid] < ele:
        return binary_search(arr, mid + 1, hig, ele)
    elif arr[mid] > ele:
        return binary_search(arr, low, mid - 1, ele)
    else:
        return mid

def insert_sort_bin(arr):
    for i in range(1, len(arr)):
        ele = arr[i]
        ind = binary_search(arr, 0, i - 1, ele)
        arr[:] = arr[:ind] + [ele] + arr[ind:i] + arr[i + 1:]
    return arr

Übrigens, wenn Sie Bisect verwenden, ein Modul für die 2-minütige Suche,

insert_sort_bin_buildin.py

import bisect
def insert_sort_bin_buildin(arr):
    for i in range(1, len(arr)):
        bisect.insort(arr, arr.pop(i), 0, i)
    return arr

Zusammenführen, sortieren

• Wiederholen Sie zuerst die Teilung und kombinieren Sie sie dann in der richtigen Reihenfolge.
• Infolgedessen erfolgt das Teilen und Verbinden rekursiv.
• Sortieren beim Kombinieren. --Wenn die sortierten Sequenzen kombiniert werden, entwickeln Sie eine Kombinationsmethode. --Heapq Merge kann auch zum Zusammenführen verwendet werden.
• Wenn Sie es bis zu einem gewissen Grad teilen können, können Sie es mithilfe eines anderen Sortieralgorithmus beschleunigen. ――Es ist ziemlich schnell, aber es verbraucht viel Speicher.
• Kann parallel verarbeitet werden

merge_sort.py

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    #Mach den Split hier
    left = arr[:mid]
    right = arr[mid:]
    
    #Rekursiv teilen
    left = merge_sort(left)
    right = merge_sort(right)
    
    #Wenn die Rückgabe zurückgegeben wird, kombinieren und übergeben Sie die nächste Kombination
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0
    
    #Sie müssen nur von links schauen, um die sortierten Arrays zusammenzuführen.
    while l_i < len(left) and r_i < len(right):
        #Hier=Die Stabilität bleibt durch Anbringen erhalten
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1
    
    #Wenn eine der oben genannten while-Anweisungen zu False wird, wird sie beendet. Erweitern Sie also zu viel
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

Schnelle Sorte

――Bestimmen Sie einen Referenzwert und teilen Sie ihn in zwei Sequenzen, groß und klein, entsprechend dem Referenzwert.

• Verwenden Sie als Methode zur Auswahl dieses Referenzwerts den Anfang oder das Ende des Arrays, den Medianwert von etwa drei geeigneten Werten usw.
• Die gleiche Verarbeitung wird innerhalb der geteilten Gruppen rekursiv durchgeführt.
• Die Leistung hängt davon ab, wie der Standardwert ermittelt wird.
• Wenn Sie es bis zu einem gewissen Grad teilen können, können Sie es mithilfe eines anderen Sortieralgorithmus beschleunigen. ――Es ist ziemlich schnell, aber es verbraucht viel Speicher.
• Keine stabile Sorte.

quick_sort.py

def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
    
    #Zufällig, da dies nicht vom Status der Daten abhängt.choice()Könnte genutzt werden.
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0
    
    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right

Sortierung zählen

--Zählen Sie die Nummer jedes Wertes.

• Einfach zu implementieren.
• Je nach Wertebereich sehr schnell.

Die Bucket-Sortierung ist ein Sortieralgorithmus, der der Zählsortierung sehr ähnlich ist. Die Bucket-Sortierung ist wie ein Sortieralgorithmus, der mehrere Boxen mit einem bestimmten Bereich erstellt, Werte in sie einfügt, jede Box sortiert und sie dann kombiniert.

Die Zählsortierung kann auch die Stabilität aufrechterhalten, indem für jeden Wert ein Feld erstellt und hinzugefügt wird. Dies ist jedoch die Implementierung, da die Idee eher ein Bucket als eine Zählung ist. Wenn Sie das Modul collection.defaultdict verwenden, können Sie es ganz einfach und stabil implementieren.

count_sort.py

def count_sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    count = [0] * (max_num - min_num + 1)
    for ele in arr:
        count[ele - min_num] += 1
 
    return [ele for ele, cnt in enumerate(count, start=min_num) for __ in range(cnt)]

Geschwindigkeitsvergleich

Zu verwendender Datensatz

Generiert mit numpy.random.

Der erstellte Datensatz ist

--data1: 100 einheitliche Zufallszahlen im Bereich von 0-100 --data2: 10000 einheitliche Zufallszahlen im Bereich von 0-1000 --data3: 10000 einheitliche Zufallszahlen im Bereich von 0 bis 100 --data4: 100 Zufallszahlen der Standardnormalverteilung mit Mittelwert 10 und Standardabweichung 5 --data5: 10000 Zufallszahlen der Standardnormalverteilung im Bereich von Durchschnitt 100 und Standardabweichung 50 --data6: 100 einheitliche Zufallszahlen im Bereich 0-100 bereits in umgekehrter Reihenfolge sortiert --data7: Bereits nach 100 einheitlichen Zufallszahlen von ganzen Zahlen im Bereich von 0 bis 100 sortiert, werden nur die ersten 10 durcheinander gebracht

make_data.py

data_rand_1 = list(randint(0, 10 ** 2, 10 ** 2))
data_rand_2 = list(randint(0, 10 ** 4, 10 ** 4))
data_rand_3 = list(randint(0, 10 ** 2, 10 ** 4))
data_rand_4 = [int(normal(10, 5)) for __ in range(10 ** 2)]
data_rand_5 = [int(normal(10 ** 2, 50)) for __ in range(10 ** 4)]
data_rand_6 = sorted(randint(0, 10 ** 2, 10 ** 2), reverse=True)
data_rand_7 = sorted(randint(0, 10 ** 2, 10 ** 2))
data_rand_7[0: 10] = choice(data_rand_7[0: 10], 10, replace=False)

Geschwindigkeitsmessung

Der folgende Code wurde verwendet, um 100 Mal zu messen, und der Durchschnitt wurde berechnet. Ich konnte es mit dem Timeit-Befehl des Jupyter-Notizbuchs nicht gut messen.

Die Einheit ist μs.

Für jeden Algorithmus wurden Messungen durchgeführt, um Fehler so weit wie möglich zu reduzieren. Vielleicht hängt es von den Spezifikationen der CPU und des Speichers ab, aber wenn die Implementierung so wäre, dass alle Algorithmen gleichzeitig mithilfe einer Schleife gemessen werden könnten, würde die Leistung erheblich sinken.

time.py

datas = [data_rand_1, data_rand_2, data_rand_3,
             data_rand_4, data_rand_5, data_rand_6, data_rand_7]

for ind, data in enumerate(datas):
    print("---- DataSet : {0} ----".format(ind + 1))
    times = []
    for i in range(100):
        start = time.time()
        #Sortieralgorithmus, den Sie messen möchten
        sorted(data)
        elapsed_time = int((time.time() - start) * (10 ** 6))
        times.append(elapsed_time)

    print(sum(times) // 100)

Berücksichtigung des Ergebnisses vorerst

• Die integrierte Sortierung von Python ist schnell.
• Die Sortierung von Einfügungen ist bei Sortierungen auf niedriger Ebene relativ schnell.
• Es wird nicht schneller, selbst wenn Sie 2 Minuten lang nach Sortierung suchen suchen. --Merge Sort und Quick Sort sind unerwartet langsam. Bei größeren Daten ist es meiner Meinung nach viel schneller, wenn Sie eine Zählsortierung in die Mitte der Schnellsortierung setzen.
• Die meisten Algorithmen haben je nach Status der Daten keine schlechten Ergebnisse, aber nur die Leistung beim schnellen Sortieren verschlechtert sich je nach Status der Daten.

Ich suche einen Algorithmus schneller als die integrierte Sortierung

Bei engen Bereichen scheint die Zählsortierung schneller zu sein als die integrierte Sortierung.

Ich denke, wenn wir die Bucket-Sortierung, die relativ zur Zählsortierung ist, erfolgreich implementieren können, können wir einen schnelleren Algorithmus erstellen.

Kombinieren Sie vorerst die schnelle Sortierung und die Zählsortierung, um eine große Datenmenge einzugeben.

Die vorbereiteten Daten sind "big_data = list (randint (0, 10 ** 3, 10 ** 6))".

quick_sort_with_count.py

def quick_sort_with_count(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
    ref = choice(arr)
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1

    if len(left) <= 1000:
        left = count_sort(left)
    else:
        left = quick_sort_with_count(left)

   if len(right) <= 1000:
        right = count_sort(right)
    else:
        right = quick_sort_with_count(right)

    return left + [ref] * ref_count + right

Abschließend

Ich habe vorerst keine Zeit mehr, das war's. Wenn Sie Zeit haben, nehmen Sie ein feinkörniges Dataset und vergleichen und validieren Sie die in Python integrierten Sortierungen und Zählsortierungen.

Es wird allgemein gesagt, dass Zusammenführungssortierung, schnelle Sortierung usw. schnell sind, aber vorerst scheint es nicht so schnell zu sein, da rekursive Aufrufe usw. in Python Zeit brauchen.

Wenn Sie den Bereich und die Art der Werte kennen, kann die Zählsortierung hilfreich sein. Wikipedia auf Japanisch hat nicht einmal einen Artikel, und einige englische Dokumente werden mit der Sortierung von Eimern verwechselt, aber ...

Referenzseite

• Wikipedia Sort: Eine umfassende Beschreibung des Sortieralgorithmus.
• Rosetta Code: Eine Sammlung von Implementierungsbeispielen für jede Algorithmussprache. Ich habe versucht, es von hier fallen zu lassen.
• Zusammenfassung der zufälligen Generierung von Numpy
• Verarbeitungszeit messen und anzeigen