Tri d'un tableau avec un nombre minimal de comparaisons

Question

J'ai besoin d'aide avec mon CS devoirs. J'ai besoin d'écrire une routine de tri qui trie un tableau de longueur 5 à l'aide de 7 comparaisons dans le pire des cas (je vous ai prouvé que le 7 sera nécessaire, en raison de la hauteur de l'arbre de décision).

J'ai envisagé d'utiliser l'arbre de décision codé, mais cela signifie que l'algorithme est vraiment compliqué et a été évoqué par mon tuteur qui n'est pas la façon dont il est censé être fait.

J'ai vérifié quicksort, de fusion et de tri, segment tri, d-ary tas de tri, le tri par insertion, tri de sélection, tous ne répondent pas à l'exigence, ce qui m'amène à croire qu'il ya un besoin pour un algorithme spécifique pour les tableaux de longueur 5.

Voudrais vraiment obtenir quelques conseils dans la bonne direction.

Answer 1

Donald Knuth est L'Art de la Programmation Informatique, le volume 3 contient une section sur exactement de ce sujet. Je n'ai pas de livres ici avec moi, mais je suis sûr que Knuth présente l'algorithme 5 éléments. Comme vous pensez, il n'y a pas un algorithme général qui donne le nombre minimal de comparaisons pour de nombreuses tailles, mais il y a un certain nombre de trucs qui sont utilisés dans de tels algorithmes.

De vagues souvenirs, j'ai reconstitué l'algorithme de 5 éléments, et il peut être effectué dans les 7 comparaisons. Tout d'abord, prendre deux paires séparées, comparer à l'intérieur de ceux-ci, et de comparer les plus petits de chaque paire. Ensuite, comparer le restant contre le plus grand des deux. Maintenant cela se divise en deux cas selon que le reste de l'élément est plus petit ou plus grand, mais dans tous les cas, il est possible de terminer dans les trois comparaisons encore disponibles.

Je recommande à dessiner des images pour vous aider. Knuth les photos sont quelque chose comme ceci:

o---o
/
o---o

qui montre les résultats obtenus après les trois premières comparaisons (et de ce que je me souviens, ce genre de photo apparaît dans de nombreux minimale de comparaison de toutes sortes). Une ligne relie deux éléments dont l'ordre que nous connaissons. Avoir de telles images vous aide à déterminer les éléments à comparer, comme vous voulez faire une comparaison qui vous donne le montant maximal de l'information.

Addendum: Depuis qu'il est accepté de répondre avec code, je suppose qu'il n'y a pas de mal dans la finition de ces diagrammes, et ils peuvent être un complément utile à la réponse. Donc, commencez par le dessus de l'un, et de comparer l'élément manquant à l'encontre de celui en haut à gauche. Si elle est plus grande, cela conduira à

/--o
o
 / \--o
o
\--o

Maintenant, comparer les deux grands éléments en haut à droite et nous nous retrouvons avec

o---o---o
/
o---o

Maintenant, en comparant le bas à droite de l'élément de première contre celui du milieu sur le dessus, puis sur le côté, elle appartient, nous la placer correctement à l'aide de deux autres comparaisons.

Si la comparaison initiale a abouti à l'élément restant étant plus petit, le schéma devient

o---o---o
/
o---o

Maintenant, comparer les deux qui ont pourtant rien de plus petits qu'eux. Une option est le dernier schéma ci-dessus, ce qui est possible avec les deux autres comparaisons. L'autre cas est

o---o
/
o---o---o

Et ici encore, celui qui n'est pas encore en séquence avec les autres peut être placé correctement avec les deux comparaisons.

Answer 2

Oui, c’est dans Knuth vol 3 page 185 (section 5.3.1). Cela a été documenté pour la première fois dans une thèse de doctorat, votre prof est donc assez dur avec vous! Il n'y a pas de méthode élégante vraiment simple; vous devez le suivre comme un arbre partiellement ordonné.

Ici c'est dans le souffle. Testé OK (SBCL sur Linux)

 (defun small-sort (a)  
  "Sort a vector A of length 5"  
  (if (> (aref a 0) (aref a 1))  
      (rotatef (aref a 0) (aref a 1)))  
  (if (> (aref a 2) (aref a 3))  
      (rotatef (aref a 2) (aref a 3)))  
  (if (> (aref a 0) (aref a 2))  
      (progn  
        (rotatef (aref a 0) (aref a 2))  
        (rotatef (aref a 1) (aref a 3))))  
  (if (> (aref a 4) (aref a 2))  
      (if (> (aref a 4) (aref a 3))  
          (progn)  
          (rotatef (aref a 3) (aref a 4)))  
      (if (> (aref a 4) (aref a 0))  
          (rotatef (aref a 2) (aref a 4) (aref a 3))  
          (rotatef (aref a 0) (aref a 4) (aref a 3) (aref a 2))))  
  (if (> (aref a 1) (aref a 3))  
      (if (> (aref a 1) (aref a 4))  
          (rotatef (aref a 1) (aref a 2) (aref a 3) (aref a 4))  
          (rotatef (aref a 1) (aref a 2) (aref a 3)))  
      (if (> (aref a 1) (aref a 2))  
          (rotatef (aref a 1) (aref a 2))  
          (progn)))  
  a)  

(defun check-sorted (a)  
  (do ((i 0 (1+ i)))  
      ((>= i (1- (array-dimension a 0))))  
    ;;(format t "~S ~S~%" (aref a i) (aref a (+ 1 i)))  
    (assert (<= (aref a i) (aref a (+ 1 i))))))  

(defun rr ()  
  (dotimes (i 100000)  
    (let ((a (make-array 5 :initial-contents (list (random 1.0) (random 1.0) (random 1.0) (random 1.0) (random 1.0) ))))  
      ;;(format t "A=~S~%" a)  
      (let ((res (small-sort a)))  
        (check-sorted res)  
        ;;(format t "Res=~S~%" res)  
        ))))
 

Answer 3

7 semble être une sorte de coquille .

Answer 4

Je ne pense pas que le hard-codée de la solution a besoin d'être compliqué tout ce que:

1. Comparer (éléments) 2 & 3, et remplacez si nécessaire
2. Comparer 3 & 4, et remplacez si nécessaire
3. Comparer 1 & 3, si 1 est de moins en moins, puis comparer 1 & 2, sinon comparer 1 & 4. Placer 1 dans la fente correcte.
4. Répétez l'étape 3 sauf avec des éléments 3 et 5.

Toujours utiliser 7 comparaisons.

EDIT:

Je ne pense pas que cela va fonctionner: l'Étape 4 est cassé, et pourrait avoir besoin d'un 8e de comparaison. Considérer:

Index | 1 | 2 | 3 | 4 | 5 |
Value | 2 | 3 | 4 | 5 | 1 |

Étape 4:

1. Comparer 3 & 5 == 4 vs 1 == l'élément 5 de moins que l'élément 3
2. Comparer 2 & 5 == 3 vs 1 == l'élément 5 de moins que l'élément 2
3. ??? Faut comparer 1 & 5 pour savoir où mettre l'élément 5.

Answer 5

Le tri par seau peut être implémenté comme algorithme de comparaison comme suit:

Prenez un élément.

Comparez-le à tous les seaux.

Déposez-le dans le seau qui correspond. <- Comparaison nécessaire.

Si le compartiment n'est pas trouvé, créez-en un nouveau.

Il s’agit donc d’un algorithme de tri dynamique de seau que je viens de décrire.

J'ai déjà inventé / décrit cela sur les groupes de discussion dans le passé.