Discussion :

[Lou E.]

Je tente de créer un merge sort en LMC (Little Man Computer) / language assembleur. J'ai beaucoup de difficultés à réaliser le triage et surtout au décalage et je suis à cours d'idées pour compléter cette boucle décalage.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
;; Ce programme lit deux séquences de nombres triées par ordre croissant et
;; renvoie la combinaison de ces deux séquences, elle aussi triée par ordre croissant.
 
premierInput (IN) ;; On entre la première séquence de nombres.
	(BRZ triageLoop)
storePremier (DAT 380) ;; On store la première séquence.
	(LDA storePremier)
	(ADD incrémenter)
	(STO storePremier)
	(LDA compteur)
	(ADD incrémenter)
	(STO compteur)
	(BR premierInput)
triageLoop (IN) ;; On commence le triage avec la 2e séquence ici.
	(BRZ affichageLoop)
	(STO temp)
	(LDA 80)
	(SUB temp)
	(BRP décalage)
	(BR triageLoop)
décalage (BR étiquette) ;; On décale la première séquence si on trouve une valeur plus petite.
	(LDA étiquette)
	(ADD incrémenter)
affichageLoop (DAT 380) ;; On affiche les résultats.
	(OUT)
	(LDA affichageLoop)
	(ADD incrémenter)
	(STO affichageLoop)
	(LDA compteur)
	(SUB incrémenter)
	(STA compteur)
	(BRZ fin)
	(BR affichageLoop)
fin (HLT)
étiquette (LDA storePremier) ;; Étiquette afin de connaître la position du dernier input.
	(ADD compteur)
	(STO étiquette)
	(BR décalage)
compteur (DAT 000)
incrémenter (DAT 001)
temp (DAT 000)

[Chevalier au taureau]

Bonjour,

Je ne connais pas ce langage mais comme personne ne répond, je me lance.

J'ai du mal à comprendre comment on insère un élément dans une liste. Je ne vois pas l'opération de comparaison entre deux éléments. Qu'est-ce que ce 80 ?

Je pose plus de questions que je n'aide, j'en ai bien conscience.

[Chevalier au taureau]

Pour répondre exactement à la question : il faut boucler sur tous les éléments de la liste à partir de l'indice d'insertion, et les écrire dans la boîte suivante. De préférence, commencer par la fin : copier le dernier élément n à n+1, puis l'élément n-1 à n, jusqu'à i.
Pour répondre plus généralement : il est possible et parfois souhaitable de construire, ailleurs, une liste qui sera la fusion des 2. Ainsi, on n'a pas de décalage à faire à chaque insertion.