Introduction à l'algorithme Implémentation de 4 types de tri en Python à partir du pseudo code de la 3ème édition

introduction

Certaines sortes sont introduites dans "Algorithm Introduction 3rd Edition (Volume 1)". Basé sur ce pseudo code

--Tri par insertion --Tri par fusion --Tri en tas --Tri rapide

Est implémenté en Python. Suivez la même procédure que le pseudo code pour imiter les noms des variables. Les arguments «A» passés à la fonction de tri décrite ci-dessous sont toutes des listes dans lesquelles les éléments sont disposés dans un ordre aléatoire.

Insérer un tri

Le tri par insertion peut être écrit comme suit:

insertion_sort.py

def insertion_sort(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i + 1] = A[i]
            i -= 1
        A[i + 1] = key
    return A

Tri par fusion

Le tri par fusion est composé de deux parties.

--MERGE: combinez deux séquences alignées en un seul tableau aligné --MERGE-SORT: Fusionnez les séquences subdivisées dans l'ordre par appel récursif

merge_sort.py

def merge(A, p, q, r):
    n_1 = q - p + 1
    n_2 = r - q
    L = []
    R = []
    for i in range(n_1):
        L.append(A[p + i])
    for j in range(n_2):
        R.append(A[q + j + 1])
    L.append(SENTINEL)
    R.append(SENTINEL)
    i, j = 0, 0
    for k in range(p, r + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return A


def merge_sort(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = (p + r) // 2
        merge_sort(A, p, q)
        merge_sort(A, q + 1, r)
        merge(A, p, q, r)
    return A

Tri de tas

Préparation: représenter le tas

Le tri de tas utilise une structure appelée tas. Tout d'abord, comme préparation préliminaire, créez une classe Heap pour représenter le tas en Python. Il s'agit de l'objet intégré de Python list avec l'ajout de l'attribut heap_size.

heap_sort.py

class Heap(list):
    def __init__(self, *args):
        super().__init__(*args)
        self.heap_size = len(self)

Ce tas garde sa fonction de liste. Essayez d'écrire:

heap = Heap([1, 2, 3, 2, 3, 4])
print("heap:", heap)
print("heap.heap_size:", heap.heap_size)
print("len(heap):", len(heap))

Le résultat de l'exécution est le suivant:

heap: [1, 2, 3, 2, 3, 4]
heap.heap_size: 6
len(heap): 6

Maintenant, tri en tas

Le tri en tas peut être effectué en 5 parties.

--LEFT: renvoie l'élément qui est l'enfant de gauche avec lui-même comme parent lorsque le tas est représenté par un arbre de deux quarts.

• DROITE: Procédure BONNE pour retourner le bon enfant avec vous-même en tant que parent --MAX-HEAPIFY: En supposant que le tas se trouve sous la racine, déplacez la racine vers une position appropriée et créez le tas entier. --BUILD-MAX-HEAP: MAX-HEAPIFY un tableau complètement aléatoire pour faire le tas entier --HEAP-SORT: Triez le tableau entier en supprimant les racines et en réparant le reste comme un tas.

À l'aide de la classe Heap créée lors de la préparation, ce sont les suivantes:

heap_sort.py

def left(i):
    return 2 * (i + 1) - 1

def right(i):
    return 2 * (i + 1)

def max_heapify(A, i):
    l = left(i)
    r = right(i)
    if l <= A.heap_size - 1 and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r <= A.heap_size - 1 and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

def build_max_heap(list_A):
    A = Heap(list_A)
    A.heap_size = len(A)
    for i in reversed(range((len(A) - 1) // 2 + 1)):
        max_heapify(A, i)
    return A

def heap_sort(list_A):
    A = build_max_heap(list_A)  #Où A devient une instance de la classe Heap
    for i in reversed(range(1, len(A))):
        A[0], A[i] = A[i], A[0]
        A.heap_size = A.heap_size - 1
        max_heapify(A, 0)
    return A

Tri rapide

Le tri rapide peut être effectué en deux parties.

--PARTITION: $ A [p..r] $ composé uniquement d'éléments sous le pivot $ A [p..q-1] $ et $ A [q + 1 .. composé uniquement d'éléments plus grands que le pivot Diviser en deux r] $ --QUICK-SORT: Appelez PARTITION récursivement pour trier la totalité de $ A [p..r] $

Le pivot est $ A [r] $, c'est-à-dire l'élément le plus à droite.

quick_sort.py

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

def quick_sort(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q - 1)
        quick_sort(A, q + 1, r)
    return A

Bonus: trier par ordre non croissant (ordre décroissant)

Les quatre types de sortes créés jusqu'à présent sont ceux qui sont les plus petits à gauche et ceux qui augmentent dans l'ordre à mesure qu'ils vont vers la droite. En prime, créez quatre types de sortes dans l'ordre inverse. Le nom de la fonction est quelque chose comme (nom de tri) _non augmentant.

Une brève explication est ajoutée en commentant la pièce réécrite à partir de la fonction de tri d'origine.

insertion_sort_nonincreasing.py

def insertion_sort_nonincreasing(A):
    for j in range(1, len(A)):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] < key:  #Et puis redirection des inégalités
            A[i + 1] = A[i]
            i -= 1
        A[i + 1] = key
    return A

merge_sort_nonincreasing.py

SENTINEL_SMALL = - float('inf')  #Rendre la garde moins l'infini

def merge_nonincreasing(A, p, q, r):
    n_1 = q - p + 1
    n_2 = r - q
    L = []
    R = []
    for i in range(n_1):
        L.append(A[p + i])
    for j in range(n_2):
        R.append(A[q + j + 1])
    L.append(SENTINEL_SMALL)  #Utilisez un garde à l'infini moins
    R.append(SENTINEL_SMALL)  #Comme ci-dessus
    i, j = 0, 0
    for k in range(p, r + 1):
        if L[i] >= R[j]:  #Réorientation des inégalités
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return A

def mergeSort_nonincreasing(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = (p + r) // 2
        mergeSort_nonincreasing(A, p, q)      #Renommez-vous
        mergeSort_nonincreasing(A, q + 1, r)  #Comme ci-dessus
        merge_nonincreasing(A, p, q, r)       #Fusionner dans un ordre non croissant
    return A

heqp_sort_nonincreasing.py

def min_heapify(A, i):  #Nom min_le faire grimper
    l = left(i)
    r = right(i)
    if l <= A.heap_size - 1 and A[l] < A[i]:  #Et puis redirection des inégalités
        smallest = l  #Passer au plus petit au lieu du plus grand
    else:
        smallest = i
    if r <= A.heap_size - 1 and A[r] < A[smallest]:  #Et puis redirection des inégalités
        smallest = r
    if smallest != i:
        A[i], A[smallest] = A[smallest], A[i]
        min_heapify(A, smallest)  # max_min au lieu de heapify_heapify


def build_min_heap(list_A):  #Nom du build_min_entasser
    A = Heap(list_A)
    A.heap_size = len(A)
    for i in reversed(range((len(A) - 1) // 2 + 1)):
        min_heapify(A, i)  # max_min au lieu de heapify_heapify
    return A


def heapSort_nonincreasing(list_A):
    A = build_min_heap(list_A)  # build_max_construire au lieu de tas_min_heap
    for i in reversed(range(1, len(A))):
        A[0], A[i] = A[i], A[0]
        A.heap_size = A.heap_size - 1
        min_heapify(A, 0)  # max_min au lieu de heapify_heapify
    return A

quick_sort_nonincreasing.py

def partition_nonincreasing(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] >= x:  #Réorientation des inégalités
            i = i + 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

def quickSort_nonincreasing(A, p=0, r=None):
    r = len(A) - 1 if r == None else r
    if p < r:
        q = partition_nonincreasing(A, p, r)  #Appelez la version non croissante
        quickSort_nonincreasing(A, p, q - 1)  #Comme ci-dessus
        quickSort_nonincreasing(A, q + 1, r)  #Comme ci-dessus
    return A