Moins de comparaisons nécessaires pour trier (ordonner) 5 éléments

Trouvez le moins de comparaisons nécessaires pour trier (ordonner) cinq éléments et concevoir un algorithme qui trie ces éléments en utilisant ce nombre de comparaisons.

Solution : il y en a 5! = 120 résultats possibles. Par conséquent, un arbre binaire pour la procédure de tri aura au moins 7 niveaux. En effet, ≥ 120 implique≥ 7. Mais 7 comparaisons ne suffisent pas. Le moins de comparaisons nécessaires pour trier (ordonner) cinq éléments est de 8.$2^h$$h$

Voici ma véritable question: j'ai trouvé un algorithme qui le fait en comparaison, mais comment puis-je prouver que cela ne peut pas être fait en comparaison?

La solution est fausse. Demuth [1; via 2, sec. 5.3.1] montre que cinq valeurs peuvent être triées en utilisant seulement sept comparaisons, c'est-à-dire que la borne inférieure "théorique de l'information" est serrée dans ce cas.

La réponse est une méthode adaptée à , pas un algorithme général. Ce n'est pas très beau non plus. Voici le schéma:$n=5$

1. Triez les deux premières paires.

2. Commandez les paires par rapport à leur plus grand élément respectif.

   Appelez le résultat ; nous connaissons et .a < b < d c < $[a,b,c,d,e]$$a<b<d$$c<d$

3. Insérez dans .[ a , b , d $e$$[a,b,d]$

4. Insérez dans le résultat de l'étape 3.$c$

La première étape prend clairement deux comparaisons, la seconde seulement. Les deux dernières étapes prennent chacune deux comparaisons; nous insérons dans une liste à trois éléments dans les deux cas (pour l'étape 4., notez que nous savons de que est plus petit que le dernier élément de la liste en main) et comparons d'abord avec l'élément central. Cela fait un total de sept comparaisons.$c<d$$c$

Puisque je ne vois pas comment écrire un "joli" pseudocode de ceci, voyez ici pour une implémentation testée (et, espérons-le, lisible).

1. doctorat thèse (Stanford University) de HB Demuth (1956)

   Voir aussi Tri électronique des données par HB Demuth (1985)

2. Tri et recherche par Donald E. Knuth; L'art de la programmation informatique Vol. 3 (2 e éd., 1998)

La limite inférieure théorique du tri basé sur la comparaison est . C'est-à-dire que pour trier éléments en utilisant uniquement des comparaisons ou il faut au moins le logarithme de base 2 de, d'où opérations.$\log(n!)$$n$$<$$>$n ! log ( 5 ! ) ≈ 6,91$n!$$\log(5!) \approx 6.91$

Puisque et , en utilisant un arbre de décision binaire, vous pouvez trier 5 éléments dans 7 comparaisons. L'arbre détermine exactement laquelle des 120 permutations vous avez, puis effectue les swaps nécessaires pour le trier.$5!= 120$$2^7= 128$

Ce n'est pas du code joli ou court, et vous devriez probablement utiliser des méthodes de génération de code pour créer l'arbre de décision et les échanges plutôt que de le coder à la main, mais cela fonctionne; et fonctionne de manière prouvée pour toute permutation possible de 5 éléments, prouvant ainsi que vous pouvez trier 5 éléments dans pas plus de 7 comparaisons.

je pensais quicksort. vous sélectionnez comme pivot l'élément qui se trouve juste être l'élément du milieu. comparer le pivot aux 4 articles restants résultant en deux piles à trier. chacune de ces piles peut être triée en 1 comparaison. sauf si j'ai fait une terrible erreur, les 5 articles ont été entièrement triés en seulement 6 comparaisons et je pense que c'est le nombre le plus petit de comparaisons nécessaires pour faire le travail. la question initiale était de trouver le moins de comparaisons pour trier 5 éléments.

Si vous pouvez tester l'algorithme, testez-le sur toutes les combinaisons de nombres. Si vous avez beaucoup de nombres, testez sur beaucoup de combinaisons aléatoires. Pas précis, mais plus rapide que toutes les combinaisons.

Minimale
a <b <c = 2
a <b <c <d = 3
a <b <c <d <e = 4

Maximum
3 ^ 3
4 ^ 4
5 ^ 5

Insérer au milieu utiliser 3-6 pour 4 chiffres.
La fusion utilise 4-5 pour 4 nombres.
La comparaison minimale par wiki est de 5 pour 4 numéros :) Pour 5, c'est 7. Vous utilisez 8, toujours autant.
https://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list
Si vous savez tout avant les comparaisons, vous pouvez descendre avec les comparaisons. Ma moyenne pour 4 numéros est de 3,96 / 1024 toutes combinaisons confondues.