Python - Sortieralgorithmen

Sortieren bezieht sich auf das Anordnen von Daten in einem bestimmten Format. Der Sortieralgorithmus gibt an, wie Daten in einer bestimmten Reihenfolge angeordnet werden sollen. Die meisten gängigen Ordnungen erfolgen in numerischer oder lexikografischer Reihenfolge.

Die Bedeutung der Sortierung liegt in der Tatsache, dass die Datensuche auf einem sehr hohen Niveau optimiert werden kann, wenn Daten sortiert gespeichert werden. Die Sortierung wird auch verwendet, um Daten in besser lesbaren Formaten darzustellen. Unten sehen wir fünf solcher Implementierungen der Sortierung in Python.

• Blasensortierung
• Zusammenführen, sortieren
• Sortieren durch Einfügen
• Shell Sort
• Auswahl Sortieren

Blasensortierung

Es ist ein vergleichsbasierter Algorithmus, bei dem jedes Paar benachbarter Elemente verglichen wird und die Elemente ausgetauscht werden, wenn sie nicht in Ordnung sind.

def bubblesort(list):

# Swap the elements to arrange in order
    for iter_num in range(len(list)-1,0,-1):
        for idx in range(iter_num):
            if list[idx]>list[idx+1]:
                temp = list[idx]
                list[idx] = list[idx+1]
                list[idx+1] = temp


list = [19,2,31,45,6,11,121,27]
bubblesort(list)
print(list)

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

[2, 6, 11, 19, 27, 31, 45, 121]

Zusammenführen, sortieren

Die Zusammenführungssortierung teilt das Array zunächst in gleiche Hälften und kombiniert sie dann sortiert.

def merge_sort(unsorted_list):
    if len(unsorted_list) <= 1:
        return unsorted_list
# Find the middle point and devide it
    middle = len(unsorted_list) // 2
    left_list = unsorted_list[:middle]
    right_list = unsorted_list[middle:]

    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)
    return list(merge(left_list, right_list))

# Merge the sorted halves

def merge(left_half,right_half):

    res = []
    while len(left_half) != 0 and len(right_half) != 0:
        if left_half[0] < right_half[0]:
            res.append(left_half[0])
            left_half.remove(left_half[0])
        else:
            res.append(right_half[0])
            right_half.remove(right_half[0])
    if len(left_half) == 0:
        res = res + right_half
    else:
        res = res + left_half
    return res

unsorted_list = [64, 34, 25, 12, 22, 11, 90]

print(merge_sort(unsorted_list))

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

[11, 12, 22, 25, 34, 64, 90]

Sortieren durch Einfügen

Beim Einfügen wird die richtige Stelle für ein bestimmtes Element in einer sortierten Liste gefunden. Zu Beginn vergleichen wir also die ersten beiden Elemente und sortieren sie, indem wir sie vergleichen. Dann wählen wir das dritte Element aus und finden seine richtige Position unter den beiden vorherigen sortierten Elementen. Auf diese Weise fügen wir der bereits sortierten Liste schrittweise weitere Elemente hinzu, indem wir sie an die richtige Position bringen.

def insertion_sort(InputList):
    for i in range(1, len(InputList)):
        j = i-1
        nxt_element = InputList[i]
# Compare the current element with next one
		
        while (InputList[j] > nxt_element) and (j >= 0):
            InputList[j+1] = InputList[j]
            j=j-1
        InputList[j+1] = nxt_element

list = [19,2,31,45,30,11,121,27]
insertion_sort(list)
print(list)

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

[2, 11, 19, 27, 30, 31, 45, 121]

Shell Sort

Bei der Shell-Sortierung werden Elemente sortiert, die nicht mit anderen übereinstimmen. Wir sortieren eine große Unterliste einer bestimmten Liste und reduzieren die Größe der Liste weiter, bis alle Elemente sortiert sind. Das folgende Programm ermittelt die Lücke, indem es sie mit der Hälfte der Länge der Listengröße gleichsetzt, und beginnt dann, alle darin enthaltenen Elemente zu sortieren. Dann setzen wir die Lücke so lange zurück, bis die gesamte Liste sortiert ist.

def shellSort(input_list):
    
    gap = len(input_list) // 2
    while gap > 0:

        for i in range(gap, len(input_list)):
            temp = input_list[i]
            j = i
# Sort the sub list for this gap

            while j >= gap and input_list[j - gap] > temp:
                input_list[j] = input_list[j - gap]
                j = j-gap
            input_list[j] = temp

# Reduce the gap for the next element

        gap = gap//2

list = [19,2,31,45,30,11,121,27]

shellSort(list)
print(list)

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

[2, 11, 19, 27, 30, 31, 45, 121]

Auswahl Sortieren

Bei der Auswahlsortierung suchen wir zunächst den Mindestwert in einer bestimmten Liste und verschieben ihn in eine sortierte Liste. Dann wiederholen wir den Vorgang für jedes der verbleibenden Elemente in der unsortierten Liste. Das nächste Element, das in die sortierte Liste aufgenommen wird, wird mit den vorhandenen Elementen verglichen und an der richtigen Position platziert. Am Ende werden also alle Elemente aus der unsortierten Liste sortiert.

def selection_sort(input_list):

    for idx in range(len(input_list)):

        min_idx = idx
        for j in range( idx +1, len(input_list)):
            if input_list[min_idx] > input_list[j]:
                min_idx = j
# Swap the minimum value with the compared value

        input_list[idx], input_list[min_idx] = input_list[min_idx], input_list[idx]


l = [19,2,31,45,30,11,121,27]
selection_sort(l)
print(l)

Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:

[2, 11, 19, 27, 30, 31, 45, 121]