Séquence de quelques algorithmes de tri

Question

Je vois dans certains examens de mi-parcours ou finaux sur MIT que la question suivante se répète et se répète de la même manière.

nous montrons un tableau dans l'étape d'un algorithme de tri.

5,3,1,9,8,2,4,7

2,3,1,4,5,8,9,7

1,2, 3,4,5,8,9,7

1,2,3,4,5,8,7,9

1,2,3,4,5,7,8,9

Quel est le type d'insertion/tri rapide/tri par fusion/tri par échange utilisé?

comment puis-je trouver une solution à cette question? ?

Edit: Je pense que c'est un peu rapide parce que chaque niveau des éléments est inférieur à pivot et certains éléments est plus grand que pivot ....

Answer 1

Dans ce cas, vous pouvez a) trouver un motif si vous pensez qu'il y en a un ou b) aller avec une simple élimination. Essayons d'éliminer:

1) il ne peut pas être tri par insertion car le tri par insertion commence au début et traite la plage [0, k] comme un sous-tableau trié de valeurs déjà vérifiées. Ensuite, il continue un par un donc nous insérons d'abord 3 avant 5 etc comme nous traitons d'abord [5] comme un sous-tableau trié de taille 1 et insérons 3 dedans car c'est la prochaine valeur dans le tableau entier.

2) tri par fusion trierait voisin d'abord comme il faudrait d'abord traiter récursive tout le tableau sous forme de tableaux à un seul élément, puis remonter l'arbre de récursivité et de fusionner neigbors donc plus comme ceci:

[3,5],[1,9],[2,8],[4,7] 
[1,3,5,9],[2,4,7,8] 
[1,2,3,4,5,6,7,8] 

[] montre quelles parties ont été triées à chaque étape.

Cela signifie qu'après un passage voisins seront triés.

3) sorte d'échange aurait également un autre ordre - la deuxième ligne devrait commencer par 3 comme vous le feriez échanger 5 et 3, puis 5 et 1 etc dans la première passe. Donc, après un passage, nous passions de 5,3,1,9,8,2,4,7 à 3,1,5,8,2,4,7,9 si ma bulle me sert bien. Nous comparons chaque paire et échangeons si l'élément à i+1 est supérieur à i. De cette façon le dernier élément sera le plus grand. 4) comme vous l'avez souligné, ceci est un tri rapide car à chaque étape, nous pouvons clairement voir que le tableau pivote autour d'une certaine valeur 4, puis vous faites pivoter la moitié gauche autour de 2 et la moitié droite autour de 5 etc. .

les parties en gras sont les modèles dont je parlais, maintenant, puisque vous les connaissez, vous pouvez facilement vérifier que l'on est :-)

Answer 2

Il devrait être tri rapide, non seulement parce que la preuve de partition, mais aussi ce fait intéressant: pour un certain niveau, seulement une partie du tableau a changé.

Maintenant, nous allons discuter de chaque algorithme:

tri par insertion vous donnera un modèle qui doivent être triés les premiers éléments, mais il est évident que nous n'avons pas ce modèle;

genre Bubble (échange de tri) gardera échanger voisins si l'ancien élément est plus grand que l'élément plus tard, et donc les derniers k éléments seront triés après k itérations. Sur la base de ces deux faits, nous n'aurons pas une paire de voisins (a, b) qui existe b < a après chaque itération. Cependant, la séquence ne suit pas cela, disons que le terme (3, 1) dans la première séquence existe toujours dans la deuxième séquence.

tri par fusion premier divise le tableau en 2 + 2 + 2 sous-zones puis fusionner en 4 + 4 et enfin un tableau trié de 8 éléments, donc tout à fait devrait prendre trois étapes, mais nous avons 4 étapes ici, donc ce ne sera pas un tri par fusion.