; Le quick sort
; vous voulez trier rapidement un tableau de mots en assembleur
; le quick sort est une des meilleures r‚ponses … ce problŠme
; Seb/The Removers vous le sert sur un plateau, profitez en !!!
; ATTENTION, cette proc‚dure est r‚cursive, veillez … r‚server une pile
; assez grande ( en gros si vous avez des problŠmes avec la pile, sa trop
; petite taille en sera certainement la cause !!! )
; ce source est facile … adapter pour trier autre chose que des mots...
; Rappel : la complexit‚ moyenne de ce tri est O(n*log(n)) pour un tableau
; de longueur n, O(n^2) dans le pire des cas ( tableau d‚j… tri‚ !! )
	MC68020
swap_w:	macro
; ‚change les ‚l‚ments d'indice \1 et \2 en utilisant \3
	move.w	(a0,\1.l*2),\3
	move.w	(a0,\2.l*2),(a0,\1.l*2)
	move.w	\3,(a0,\2.l*2)
	endm	

quick_sort:
; en entr‚e : 
;		- a0.l ( adresse d'un tableau de mots )
;		- d0.l=plus petit indice du tableau
;		- d1.l=plus grand indice du tableau
.qsort:
	move.l	d1,d2
	sub.l	d0,d2		; taille strictement positive ??
	ble.s	.end_qsort	; si il y a plus d'un ‚l‚ment
	move.l	d0,d2		; on trie ( rapidement ! )
	move.l	d2,d4		; d2 sert de compteur
	move.w	(a0,d4.l*2),d3	; d4 est l'indice du pivot et d3 sa valeur
	addq.l	#1,d2		
.pivot:
	cmp.l	d2,d1
	blt.s	.end_pivot	; tant qu'on est sous la limite sup‚rieure
	cmp.w	(a0,d2.l*2),d3	; compare au pivot
	ble.s	.no_swap	; si pivot plus petit -> rien
	addq.l	#1,d4		; sinon le pivot avance
	swap_w	d2,d4,d5	; et on ‚change les valeurs
.no_swap:
	addq.l	#1,d2
	bra.s	.pivot		; bouclons
.end_pivot:
	swap_w	d0,d4,d5	; on met le pivot … la bonne place !!

	movem.l	d1/d4,-(sp)	; sauvons le pivot et la borne sup
	subq.l	#1,d4
	move.l	d4,d1
	bsr	.qsort		; 'r‚cursivons' sur g,i-1
	movem.l	(sp)+,d1/d4	; on r‚cupŠre les valeurs sauv‚es...
	addq.l	#1,d4
	move.l	d4,d0
	bsr	.qsort		; puis sur i+1,d
.end_qsort:
	rts