+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Quicksort (/showthread.php?tid=6852)
Pages :
1
2
Quicksort - niahoo - 30-11-2013
Hello,
Quelqu'un pourrait-il me donner une implémentation de quicksort dans son langage favori ? Bien sûr, sans reprendre du code existant, en implémentant soi-même l'algo. Et uniquement avec la bibliothèque standard.
J'aimerais bien voir du ruby, du javascript
merci !
RE: Quicksort - srm - 02-12-2013
Ca n'est pas de moi, mais je le ferais comme ça :
def sort(list: List[Int]): List[Int] = {
list match {
case Nil => list
case _ => sort(list.tail.filter(_ <= list.head)) ::: list.head :: sort(list.tail.filter(_ > list.head))
}
}
RE: Quicksort - Sephi-Chan - 02-12-2013
A défaut d'avoir des implémentations perso (est-ce très pertinent pour ces algos très classiques, d'autant qu'il y a des variantes selon le choix du pivot ?), voici une collection d'implémentations dans différents langages, dont Ruby et Javascript, que je colle ici par commodité :
function qsort(a) {
if (a.length == 0) return [];
var left = [], right = [], pivot = a[0];
for (var i = 1; i < a.length; i++) {
a[i] < pivot ? left.push(a[i]) : right.push(a[i]);
}
return qsort(left).concat(pivot, qsort(right));
}
def quicksort(list)
return list if list.length <= 1
pivot = list.shift
left, right = list.partition { |el| el < pivot }
quicksort(left) + [pivot] + quicksort(right)
end
RE: Quicksort - niahoo - 02-12-2013
Ben l'idée c'est de voir comment chacun implémente le truc pour progresser. Là effectivement la skill copier-coller progresse mais bon je suis déjà au top là-dessus :p
Sinon la version ruby est sympa. Le retour de lists.partition c'est un tuple ou une liste ?
RE: Quicksort - Sephi-Chan - 02-12-2013
C'est 2 listes (Enumerable#partition). D'un côté les éléments dont le test à retourné true, de l'autre ceux pour lequel ça a retourné false.
RE: Quicksort - srm - 02-12-2013
J'ai vu différentes implémentation de quickSort en Scala, j'ai pris celle que j'aurais fait
RE: Quicksort - niahoo - 03-12-2013
Oui sephi j'avais compris, mais ces deux listes justement, viennent-elles sous forme d'une liste contenant deux listes, ou d'un tuple contenant deux listes ?
Oxman ta solution exécute deux filtres sur toute la liste, elle est donc parcourue deux fois en entier. C'est élégant à l'écriture mais moins efficace. Peux-tu me montrer la version optimisée ?
RE: Quicksort - Sephi-Chan - 03-12-2013
Ça retourne un tableau unique en réalité, et Ruby te permet de capter les éléments séparément via l'assignation parallèle.
RE: Quicksort - srm - 03-12-2013
def sort(list: List[Int]): List[Int] = {
list match {
case Nil => list
case _ => {
val (low, high) = list.tail.partition(_ <= list.head)
sort(low) ::: list.head :: sort(high)
}
}
}
Que voilà
RE: Quicksort - niahoo - 04-12-2013
Ok merci
Sephi, si en ruby on voulait uniquement les éléments plus petits, peut-on accéder directement à l'un des éléments du retour de la fonction ?
do_something_with_left(list.partition({ |el| el < pivot })[0])
Oxman, le triple colon colle deux listes, que fait le double colon ?