[GO] Fusion de la mise en œuvre du tri / analyse du montant du calcul et de l'expérimentation en Python
Cette fois, je parlerai du tri par fusion (en utilisant la gouvernance fractionnée) de l'algorithme de tri. L'algorithme de tri est un algorithme qui trie les éléments de la structure de données dans l'ordre croissant ou décroissant, et le tri par fusion est l'un des algorithmes les plus courants.
Explication de l'algorithme
Dans le tri par fusion, le tri est essentiellement effectué à l'aide d'un tableau, mais comme son nom l'indique, le tableau est divisé puis mélangé. En faisant ce mélange, nous comparerons et trierons chaque élément. En conséquence, vous obtenez un tableau trié.
Divisé
Tout d'abord, lors du fractionnement, recherchez la valeur au milieu du tableau avec mid = (low + high) / 2. Par exemple, lorsque la longueur du tableau est n, mid = (0+ (n-1)) / 2 est la valeur médiane, et il est divisé en deux tableaux de 0 à milieu et milieu + 1 à n-1. Est répété et la division se termine lorsque la longueur du tableau devient 1. Dans la division, chaque séquence est divisée en deux séquences, donc une longue séquence est le parent et deux courtes séquences de même longueur sont les enfants, comme dans la structure de bifurcation. Imaginez que cela crée une arborescence log (n) avec une profondeur de 2.
Gouvernance
Lors de la gouvernance, les premiers éléments des deux tableaux enfants sont comparés et placés au début de la liste parent. Il incrémente ensuite l'index accédé de la liste contenant l'élément sélectionné de un, compare le deuxième élément avec le premier élément de un et le stocke dans l'index suivant de la liste parente. La valeur de l'index sélectionné de cette manière est incrémentée, le travail de stockage dans la liste parent est répété jusqu'au dernier élément de l'une ou l'autre des listes enfants, et les éléments de la liste avec les éléments restants sont stockés dans l'ordre. En répétant ceci dans l'ordre du nœud final de l'arborescence au nœud racine, le tableau trié par le dernier nœud racine est terminé.
À la fin, je publierai un site Web qui explique de manière facile à comprendre avec des graphiques.
la mise en oeuvre
J'ai implémenté brièvement une fonction de tri par fusion, je vais donc l'expliquer. J'ai ajouté le numéro de ligne de 1 dans le commentaire sur le côté droit de chaque ligne.
merge_sort.py
def merge(array): # line1
mid = len(array) # line2
if mid > 1: # line3
left = merge(array[:(mid/2)]) # line4
right = merge(array[(mid/2):]) # line5
array = [] # line6
while len(left) != 0 and len(right) != 0: # line7
if left[0] < right[0]: # line8
array.append(left.pop(0)) # line9
else: # line10
array.append(right.pop(0)) # line11
if len(left) != 0: # line12
array.extend(left) # line13
elif len(right) != 0: # line14
array.extend(right) # line15
return array # line16
-Je l'ai fait en supposant que la valeur prise par le paramètre dans line1 est un tableau contenant uniquement des entiers dans l'élément.
-J'ai demandé la valeur de la longueur du tableau avec line2, mais c'est un peu différent de l'explication ci-dessus car j'ai créé un nouveau tableau à chaque fois que je l'ai divisé avec Python. Dans le cas d'un tableau tel que JAVA, il est divisé lors du calcul du numéro d'index d'un tableau avec un objet invariant, donc trouvez-le par la méthode décrite ci-dessus.
-En ligne3, il est jugé si la longueur du tableau est plus longue que 1 ou plus, si elle est longue, le code de ligne4 à ligne15 est exécuté, et s'il est court, le tableau est renvoyé tel quel en tant que valeur de retour.
-Dans les lignes 4 et 5, la fonction est appelée en donnant au paramètre un tableau qui coupe récursivement la liste parent en deux.
-Comme vous pouvez le voir dans le code jusqu'à présent, en appelant la fonction de manière récursive, le tableau est divisé jusqu'à ce qu'il devienne 1.
-La raison pour laquelle le tableau parent est vide en ligne6 est que la méthode append () (ajouter un élément à la fin de la liste) est utilisée pour mettre une valeur dans la liste après cela. Le tableau d'origine contenait déjà des éléments et j'ai pensé qu'il serait peu pratique d'ajouter des éléments.
-Line7 a utilisé une boucle, mais elle continuera à boucler à moins qu'une des listes ne soit vide.
-Comparez les premiers éléments des deux tableaux sur les lignes 8 à 11, supprimez le premier élément du tableau contenant des éléments plus petits et ajoutez-le à la fin du tableau parent. Continuez ce processus jusqu'à ce que l'une des listes soit vide.
-Dans les lignes 12 à 15, une liste devient vide lorsque la boucle de la ligne 7 se termine, mais l'autre liste laisse au moins un élément, donc les éléments restants de l'un ou l'autre des tableaux sont rassemblés dans la liste parent. En plus de.
-Dans line16, retourne chaque tableau trié comme valeur de retour, trie le tableau parent de chaque tableau, et lorsque le nœud racine est atteint, renvoie tous les éléments de la séquence donnée au paramètre dans un état trié. Je vais.
Montant du calcul
Soit T (n) la quantité totale de calcul dans le tri par fusion, où n est le nombre d'éléments dans le tableau ou la longueur du tableau. Puisque T (0) et T (1) ne font rien, le montant du calcul est de 0. Dans le tri par fusion, le tableau est d'abord divisé par deux et le tri par fusion est appelé récursivement, donc T (n / 2) le fait deux fois avec le montant du calcul (lignes 4 et 5) lorsqu'il est appelé récursivement, donc T (n / 2) ) + T (n / 2) = 2 Lorsque T (n / 2) appelle les deux (ligne4 ~ 5). En plus de cela, le tri par fusion effectue une boucle n-1 fois dans le pire des cas, donc le montant total du calcul est T (n) = 2T (n / 2) + n -1. Vous connaissez maintenant la quantité de calcul lorsque la longueur du tableau de tri par fusion est n, mais comme le tri par fusion est appelé récursivement en divisant par deux le tableau, T (n / 2), T (n / 4), T (n / 8) ・ ・ ・ ・ ・ ・ ・ ・ ・ Nous vérifierons également le montant du calcul lorsque T (n / (2 ^ (k-1))). k est le nombre de fois où il est appelé récursivement et commence à k = 1. T(n/2) = 2T(n/4) + n/2 - 1, T(n/4) = 2T(n/8) + n/4 - 1, T(n/8) = 2T(n/16) + n/8 - 1, ・ ・ ・ ・ ・ T(n/2^(k-1)) = 2T(n/2^k) + n/2^(k-1) - 1 Est le montant du calcul lorsque k> = 1.
Substituer ceci dans l'équation de T (n) donne: T(n) = 2(2T(n/4) + n/2 - 1) + n - 1 = 4T(n/4) + 2n - (1 + 2) = 4(2T(n/8) + n/4 - 1) + 2n - (1 + 2) = 8T(n/8) + 3n - (1 + 2 + 4) = 8(2T(n/16) + n/8 - 1) + 3n - (1 + 2 + 4) = 8T(n/8) + 4n - (1 + 2 + 4 + 8) ・ ・ ・ ・ ・ = 2 ^ kT (n / 2 ^ k) + k * n- (1 + 2 + 4 + ・ ・ ・ ・ ・ + 2 ^ (k-1)) Ce sera.
avec ça T (n) = 0, si n = 0,1 T (n) = 2 ^ kT (n / 2 ^ k) + (k * n --k) - (1 + 2 + 4 + ・ ・ ・ ・ ・ + 2 ^ (k-1)), Il s'avère que si 2 <= n <= k.
Ici, le fait que les appels récursifs soient faits k fois signifie qu'il y a k couches dans la structure arborescente, et on peut dire que 2 ^ k est la valeur de n dans la k couche. Par conséquent, lorsque n = 2 ^ k et que cela est résolu pour k, k = log (n), et lorsque ceux-ci sont substitués dans l'équation de T (n), T (n) = nT (2 ^ k / 2 ^ k) + log (n) * n --log (n) - (1 + 2 + 4 + ・ ・ ・ ・ ・ + 2 ^ (log (n) -1) )) = nT(1) + nlog(n) - log(n) - (2^log(n) - 1) = nlog(n) - log(n) - (2^log(n) - 1)
Le premier terme est de T (1) = 0 à n * 0 = 0, et le dernier terme provient de la formule de somme (voir Wikipedia). Puisque nlog (n)> 2 ^ log (n), l'ordre de calcul est O (nlog (n)). En passant, dans le tri par fusion, le montant moyen du calcul et le meilleur montant de calcul sont identiques au pire montant de calcul.
Graphisme
Puisque le temps moyen a été réellement calculé et représenté graphiquement, je vais afficher le code source et le graphique.
merge_sort.py
import math
import random
import time
import matplotlib.pyplot as plt
#Copiez la fonction de tri par fusion ici
sumOfTime = 0
sumPltList = []
nlognList = []
list1 = []
#Boucle pour créer des longueurs de tableau 0-3000
for i in range(3000):
#Boucle pour fusionner et trier 100 fois pour chaque tableau de longueur i
for j in range(100):
#0 pour chaque index~Entrez un nombre aléatoire de 100000
for k in range(i):
list1.append(random.randint(0,100000))
#Temps avant le tri par fusion
t0 = time.clock()
merge(list1)
#Temps après le tri par fusion
t1 = time.clock()
#Vider le tableau pour le prochain tri de fusion
list1 = []
#Somme des différences de temps lors du tri par fusion
sumOfTime += t1 - t0
#Valeur moyenne de 100 tris de fusion
sumOfTime /= 100
#Il n'y a aucune base car je stocke le temps moyen dans la liste et 2000000 est la queue du livre.
sumPltList.append(sumOfTime*2000000)
# log(0)Gérer ilog(i)Stocker i dans la liste pour comparaison
if i != 0:
nlognList.append(i*math.log(i)/math.log(2))
else:
nlognList.append(0.0)
#Réinitialisez le temps total toutes les 100 fois
sumOfTime = 0
#Fusionner le tri et le nlog(n)Tracez une courbe
plt.plot(sumPltList, "r-", label = "Merge_Sort")
plt.plot(nlognList, "g-", label = "O(nlogn)")
#Afficher l'étiquette en haut à gauche
plt.legend(loc=2)
#Attachez des étiquettes à l'axe des x et à l'axe des y
plt.xlabel('number of elements in a list')
plt.ylabel('time be taken')
#Affichage du graphique
plt.show()
La multiplication de 2000000 par le temps moyen est ajustée en regardant les résultats jusqu'au tableau de longueur 99, mais le graphique ci-dessous montre ce qui se passe avec les résultats jusqu'à 3000 de longueur.
Puisque la valeur du montant de calcul de 100 à 3000 en longueur est également proche de la valeur de nlog (n), on peut dire que l'expérience de montant de calcul est réussie.
Cette fois, j'ai expliqué, implémenté et analysé l'algorithme de tri par fusion, mais si vous trouvez quelque chose qui ne va pas ou n'est pas clair, veuillez commenter ou m'envoyer un e-mail. Je vous remercie. La prochaine fois, j'implémenterai des instructions Python ou d'autres algorithmes en Python. Merci d'avoir lu jusqu'au bout!
Lien de tri de fusion: http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/merge-sort.html
Recommended Posts