[PYTHON] Comprenez le processus de tri par fusion. Démontez finement en suivant le flux.

Qu'est-ce que le tri par fusion?

Un type de tri. Tri stable. Il utilise la méthode de division et de conquête.

--Divisez le tableau à trier en deux ――Répétez la division en deux jusqu'à ce qu'il y ait un élément (divisez) --Comparer chaque élément principal et fusionner avec le plus petit nombre vers l'avant (résoudre, fusionner) --Comparez les premiers nombres des éléments triés et fusionnez-les côte à côte (conquérir, fusionner)

Référence: Kagoshima University HP

## Fusionner le code de tri

python

#Fusionnez après le démontage dans les plus petites unités. Répétez ce processus
def merge_sort(arr):
  #Si l'élément est 1 ou 0, le tableau est renvoyé tel quel. (Parce qu'il n'y a pas de cible de comparaison et qu'il n'y a pas besoin de tri)
  if len(arr) <= 1:
    return arr
  
  #Divisez en deux. Extraire uniquement la partie entière à séparer par découpage
  mid = len(arr)//2
  
  #Divisez le tableau d'origine en deux
  arr1 = arr[:mid]
  arr2 = arr[mid:]

  #Continuez à diviser en deux jusqu'à l'unité minimale
  #La récurrence se termine quand elle devient retour
  arr1 = merge_sort(arr1)
  arr2 = merge_sort(arr2)

  return merge1(arr1, arr2)


#Comparez les deux éléments et placez le plus petit en premier
def merge1(arr1,arr2):
  #Array pour mettre le résultat de la fusion
  merged = []
  l_i, r_i =0,0

  while l_i < len(arr1) and r_i < len(arr2):

        if arr1[l_i] <= arr2[r_i]:
            merged.append(arr1[l_i])
            l_i += 1
        else:
            merged.append(arr2[r_i])
            r_i += 1

  if l_i < len(arr1):
      merged.extend(arr1[l_i:])
  if r_i < len(arr2):
      merged.extend(arr2[r_i:])
  return merged

Vérification

list=[7,4,3,5,6,1,2]
merge_sort(list)

#[1, 2, 3, 4, 5, 6, 7]

## Fusionner les détails du tri Puisque deux fonctions sont en cours d'exécution, c'est difficile à comprendre, alors décomposons-le.

1. Fonction pour créer la plus petite unité (div_arr)
2. Une fonction (fusion) qui ajoute la plus petite au tableau.

Fonction pour faire la plus petite unité

Tout d'abord, considérons une fonction qui divise chaque élément.

python

def div_arr(arr):
  #Si l'élément est 1 ou 0, le tableau est renvoyé tel quel. (Parce qu'il n'y a pas de cible de comparaison et qu'il n'y a pas besoin de tri)
  if len(arr) <= 1:
    return print(arr)
  
  #Divisez en deux. Extraire uniquement la partie entière à séparer par découpage
  mid = len(arr)//2
  
  #Divisez le tableau d'origine en deux
  arr1 = arr[:mid]
  arr2 = arr[mid:]

  #Continuez à diviser en deux jusqu'à l'unité minimale
  #La récurrence se termine quand elle devient retour
  arr1 = div_arr(arr1)
  arr2 = div_arr(arr2)

Vérification

list=[7,4,3,5,6,1,2]
div_arr(list)

[7]
[4]
[3]
[5]
[6]
[1]
[2]

Le but est de préparer deux, arr1 et arr2. La valeur entrée dans la fonction est divisée en deux, et le traitement est toujours stocké à l'arrière (arr2).

Par conséquent, même après que arr1 se termine par un retour, le traitement continue autant que arr2 est stocké.

Je m'attendais à ce que le tableau soit sorti avec return arr, mais comme rien n'est affiché, je l'ai réglé sur return print (arr). (Je ne sais pas pourquoi ça n'apparaît pas ...)

### (Référence) Lorsque le traitement récursif est effectué uniquement dans la première ligne

python

def div_arr(arr):
  if len(arr) <= 1:
    return print(arr)
  
  mid = len(arr)//2
  
  arr1 = arr[:mid]

  arr1 = div_arr(arr1)

python

list=[7,4,3,5,6,1,2]
div_arr(list)

[7]

Puisque seul arr1 est traité, seul [7] est sorti.

• Il ne devient pas [7], [4], [3]. Parce que [4] et [3] sont alloués à arr2 tout en répétant le processus récursif.

## Une fonction qui ajoute la plus petite au tableau

python

#Comparez les deux éléments et placez le plus petit en premier
def merge1(arr1,arr2):
  #Array pour mettre le résultat de la fusion
  #La valeur initiale est 0, mais le contenu augmente chaque fois que la fusion est répétée.
  merged = []

  #Valeur initiale du numéro de tableau de l'élément à comparer
  l_i, r_i =0,0

  #Condition de fin de boucle. Comparaison de tous les deux tableaux et fin
  while l_i < len(arr1) and r_i < len(arr2):

    #Si l'élément avant est plus petit
    #S'ils sont identiques, donnez la priorité à l'autre partie
        if arr1[l_i] <= arr2[r_i]:
            merged.append(arr1[l_i])
            #Ajoutez 1 au numéro de séquence afin que le même élément ne soit pas vérifié à nouveau.
            l_i += 1
        else:
            merged.append(arr2[r_i])
            r_i += 1

  #Lorsque l'instruction while se termine, ajoutez la réponse entière qui n'a pas été ajoutée.
  #Étant donné que chaque tableau a déjà été trié par ordre croissant, il est ajouté tel quel.
  if l_i < len(arr1):
      merged.extend(arr1[l_i:])
  if r_i < len(arr2):
      merged.extend(arr2[r_i:])
  return merged

Vérification

a=[2,3]
b=[1,8,9]

merge1(a,b)

#[1, 2, 3, 8, 9]

## Visualisez l'ensemble du flux de traitement Sur la base des deux processus ci-dessus, examinons le processus de merge_sort.

python

#Tableau à trier
arr=[7,4,3,5,6]

#Premier processus
arr1=[7,4]
arr2=[3,5,6]

#Récursif arr1
arr1`=[7]
arr2`=[4]

##Solution de arr1##
merge`=[4,7]


#Récursif arr2
arr1``=[3]
arr2``=[5,6]

#arr2``Se répète
arr1```=[5]
arr2```=[6]

##arr2``Solution de##
merge``=[5,6]

##Solution de arr2##
merge```=[3,5,6]


## Enfin la solution d'Arr ##
merge=[3,4,5,6,7]

## La solution de arr est une fusion de arr1 et arr2
# Solution de la fusion arr1` = [4,7]
#fusion de solution arr2```=[3,5,6]

C'est compliqué. ** Les 3 dernières lignes sont importantes **

python

  arr1 = merge_sort(arr1)
  arr2 = merge_sort(arr2)

  return merge1(arr1, arr2)

La valeur fusionnée (résultat de merge1) est entrée dans arr1 et arr2 chaque fois que merge_sort est effectué.

Il sera davantage fusionné.

Avec cela, les éléments décomposés à l'unité minimale sont réassemblés.

La personne qui a pensé que c'était incroyable et la personne qui comprend cela est également incroyable