Comment organiser correctement et sans problème une pile d'enregistrements d'observations désordonnés ?
Comparez d'abord quel enregistrement est le plus ancien, puis déplacez l'intégralité de l'enregistrement et voyez de vos propres yeux comment les données sont organisées.
Algorithmes généraux et calcul numérique
Après avoir pris une série de photos, la fiche d'enregistrement a été brouillée. Chaque carte comporte un numéro et une lettre d'identité. Si vous souhaitez les trier du plus petit au plus grand, vous ne pouvez pas perdre deux cartes portant le même numéro.
Devinez d'abord
La valeur de tri des deux enregistrements d'observation est 2. L'un d'entre eux doit-il être supprimé lors du tri ?
Afficher la réponse et les explications
Non, les deux enregistrements doivent être conservés. — Des valeurs identiques ne signifient pas des enregistrements identiques ; le tri modifie uniquement l'ordre et n'est pas responsable de la déduplication.
Ensuite, connectez l'expérience et la science
Commençons par étaler les enregistrements
Les lettres de chaque carte enregistrent l'identité et les chiffres servent de base au tri. Le même numéro peut apparaître plusieurs fois et l’enregistrement ne peut pas être supprimé.
L'entrée est un ensemble d'enregistrements, pas seulement des nombres différents.
N'effectuer qu'une seule action spécifique à la fois
La progression du mouvement, les cartes comparées ou échangées sont surlignées en orange. Le programme examine uniquement les valeurs pendant la phase de comparaison et déplace les enregistrements complets pendant la phase d'échange.
Comparer → décider d'échanger
Si vous changez d'approche, le résultat sera le même
Le livre original propose un échange par paire, en trouvant le plus petit en premier et un tri rapide par partition. Différentes étapes peuvent obtenir la même valeur ascendante, mais les enregistrements ayant la même valeur peuvent ne pas conserver l'ordre d'origine.
SIMPLE / BETTER / QUICKSORT
À mesure que les données augmentent, le nombre d'étapes devient plus important
Le nombre de comparaisons des deux premières méthodes augmente avec N² ; le tri rapide concerne généralement N log N, mais il n'est pas garanti qu'il soit le plus rapide pour chaque entrée. Le décompte est la mesure réelle dans cet exemple, et non le nombre de secondes pendant lesquelles la machine fonctionne.
Il convient de distinguer le nombre de comparaisons, d'échanges et la consommation de temps réelle
Développer le calcul
排序后：key₁ ≤ key₂ ≤ … ≤ keyₙ 排序前后：每条Enregistrer的身份与内容保持完整
Il s'agit d'une classe de règles d'algorithme, et il n'existe aucune formule astronomique pouvant être obtenue par substitution. La comparaison détermine l'ordre et l'échange doit déplacer l'intégralité de l'enregistrement ; la même valeur de clé ne signifie pas que l'enregistrement peut être supprimé.
essaie-le
Utilisez le même jeu de cartes pour comparer les trois méthodes ; faites glisser la progression à 100%, vérifiez que les nombres sont dans l'ordre croissant et que les enregistrements A-H sont toujours là.
Pas besoin de mémoriser les symboles
- N
- Nombre d'enregistrements, l'écran pour cette leçon est 8
- Comparer
- Afficher l'ordre de deux valeurs ; le tri rapide se compare également à la valeur de base
- échange
- Échangez les deux enregistrements complets
- valeur de base
- Le tri rapide est utilisé pour diviser les valeurs des deux côtés
- stabilité
- Si les enregistrements avec la même valeur de tri conservent l'ordre relatif d'origine
Algorithme, précision et champ d'application
Livre original, chapitre 6, pages imprimées 55 à 58, tableau 6.A. Trois algorithmes sont implémentés : SIMPLE SORT compare et échange paire par paire en fonction des positions avant et arrière, BETTER trouve d'abord la valeur minimale restante puis échange, et QUICKSORT utilise un partitionnement à double pointeur et une pile explicite basée sur la valeur de l'élément intermédiaire. Cette leçon omet les détails du BASIC original en optimisant l'ordre de la pile en fonction de la longueur de l'intervalle, et conserve les résultats de partition et les traces réelles de comparaison/échange ; il ne prétend pas que le pire cas de tri rapide est N log N. Les numéros de carte de démonstration n'ont pas d'unités de date réelles, les lettres marquent uniquement les identités. Les pourcentages de progression correspondent aux étapes discrètes de l'algorithme et affichent le véritable numéro d'étape. Les comparaisons et les échanges sont comptés séparément, à l'exception des secondes en cours ; il n'est pas garanti que l'ordre des enregistrements ayant la même valeur soit stable. L'introduction au tri de chaînes ASCII à la fin du chapitre est expliquée dans le texte, et l'interaction n'implémente que le tri numérique. L'AA+ local n'a pas trouvé le module spécial pour le tri, et les résultats ont été vérifiés à l'aide d'un tri numérique natif indépendant et d'invariants de permutation par étape.
vérification de ma compréhension
Lors de la comparaison de deux enregistrements, les données doivent-elles être échangées immédiatement ?
incertain — La comparaison et l'échange sont des actions différentes, et elles ne sont échangées que lorsque les conditions de l'algorithme sont remplies.
Si les nombres après tri sont les mêmes, cela signifie-t-il que l'ordre des enregistrements ayant la même valeur doit également être le même ?
incertain — Le fait de conserver ou non la relation de séquence des enregistrements ayant la même valeur implique la stabilité ; les trois implémentations de cette leçon ne fournissent pas de garanties de tri stables.
Le nombre de secondes mesuré sur l'ordinateur d'origine peut-il être directement utilisé comme temps pris par la page Web d'aujourd'hui ?
Ne peut pas — Le matériel, les langages et les implémentations varient ; cette leçon compare le nombre d'opérations reproductibles et le nombre de secondes sans réutiliser l'ancienne machine.
Le tri garantit d'abord que les enregistrements sont complets et dans le bon ordre, puis compare les coûts d'exploitation ; les enregistrements avec les mêmes valeurs ne peuvent pas être supprimés en tant que déchet en double.
Jean Meeus · Astronomical Algorithms, 2nd ed. · Non. 6 chapitre
Algorithmes généraux et calcul numérique · Tous les cours interactifs