Quicksort

[niahoo]

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 !

[srm]

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))

        }

    }

[Sephi-Chan]

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

[niahoo]

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 ?

[Sephi-Chan]

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.

[srm]

J'ai vu différentes implémentation de quickSort en Scala, j'ai pris celle que j'aurais fait

[niahoo]

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 ?

[Sephi-Chan]

Ç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.

[srm]

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à

[niahoo]

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 ?