Discussion :

[stendhal666]

Bonjour,

Originaire de c++ j'ai un peu de mal à me retrouver en LISP et fais qqs petits algorithmes pour me lancer. Un simple qsort pas optimal, mais je n'obtiens qu'un stack-overflow:

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
 
(defun qsort (l)
	   (if (= (length l) 1)
	       l
	       (append
		(qsort (lowerpart l (pivot l)))
		(qsort (upperpart l (pivot l))))))
 
(defun lowerpart (l r)
	   (let ((return-value '()))
	     (dolist (e l)
	       (if (<= e r)
		   (push e return-value)))
	     return-value))
 
(defun upperpart (l r)
	   (let ((return-value '()))
	     (dolist (e l)
	       (if (> e r)
		   (push e return-value)))
	     return-value))
 
(defun half (l)
	   (truncate (/ (length l) 2)))
 
(defun pivot (l)
	   (nth (half l) l))

Je suis preneur de conseils, merci!

PS: sous Emacs CLISP, quand je décide de réinitialiser le thread, je n'arrive plus à relancer la boucle REPL; du coup j'éteins et rallume Emacs, qqn connaît-il une solution plus pratique? Merci encore

[jack-ft]

Que donne ceci:

Code :

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

(let ((l '(42 42))) (lowerpart l (pivot l)))

Pour qu'un algorithme récursif ait une chance de terminer (un jour), il faut absolument que les données "diminuent" d'une itération à l'autre...

[EDIT]
Petite remarque: ton algorithme est en O(n*n) alors que quicksort est en O(n*log(n))... ce n'est donc pas quicksort...

Après vérification, ton algorithme est bien quicksort et il est bien en O(n*log(n))!

En effet, au premier "tour", on fait N-1 comparaisons et on obtient 2 listes qui contiennent en tout N éléments.
Aux "tours" suivants (en cumulant ce qui se passe pour chacune des sous-listes), on fait aussi N-1 comparaisons qui conduisent à 4 sous-listes.
Le nombre de "tours" est égal au nombre de fois qu'il faut diviser N par 2 pour n'obtenir que des singletons, ce qui est, dans le meilleur des cas (où, à chaque fois, les 2 moitiés ont plie poil la même taille), justement la définition du log de N en base 2.
Dans le pire des cas, à chaque découpe, on isole un seul élément, ce qui demande donc N-1 étapes pour arriver à des singletons, d'où o(n*n).
[/EDIT]

Dans emacs, as-tu essayé de tuer le buffer? C-x k

[stendhal666]

Très juste. Voilà ce que ça fait de traduire sans réfléchir un algo c en LISP...
Il me semblait en revanche que ce modèle de tri récursif était appelé qsort, la complexité supplémentaire viendrait-elle des fonctions lowerpart / upperpart qui répètent l'opération sur l'ensemble de la liste?
Saurais-tu où je pourrais trouver des exemples de programmation "à la LISP" pour en comprendre l'esprit?
Merci de ton aide