Saurez-vous trier aussi bien que V8 ?

Cette semaine, c'est Jonathan qui vous propose un #KataOfTheWeek : Le quicksort

Briefing du Kata : ## Introduction

Il existe de nombreux algorithmes de tri : le tri par tas, le tri à bulle, le tri par fusion, etc. L'efficacité de ces algorithmes est généralement mesurée grâce à leur complexité algorithmique (O(complexité)). Un autre point important à connaître lorsqu'on utilise un algorithme de tri est sa stabilité, c'est à dire s'il ne modifie pas l'ordre initial des clés identiques.

Nous allons nous intéresser ici au quicksort, qui est le tri initialement utilisé par V8, le moteur Javascript de Google, pour les tableaux contenant plus de 10 éléments (c'est le tri par insertion qui est utilisé sinon). L'algorithme quicksort a un défaut, il n'est pas stable. Ce comportement contraignant a poussé les équipes de V8 à utiliser un autre algorithme de tri, le Timsort (depuis fin 2018). C'est un algorithme qui combine le tri par fusion et le tri par insertion.

Fonctionnement

L'algorithme quicksort est un algorithme de type Diviser pour régner. Un élément pivot va être utilisé pour récursivement diviser le tableau.

• Trouver l'élément pivot (plusieurs façons de le faire, ici ça sera le dernier élément du tableau)
• Créer deux nouveaux tableaux, puis itérer sur le tableau à trier : tous les éléments plus petits que le pivot se retrouvent dans le 1er tableau, tous les éléments plus grands au pivot dans le deuxième tableau. Le pivot doit être exclu de ces comparaisons
• Concaténer le tableau des plus petits éléments (à trier par récursion) avec le pivot puis avec le tableau des plus grands éléments (à trier par récursion)

Vous l'aurez compris, cet algorithme est récursif. Il ne vous reste donc plus qu'à trouver sa condition d'arrêt et à trouver une implémentation cohérente au vu des explications ci-dessus ! Pour simplifier, vous pouvez déjà commencer par écrire une implémentation pour trier un tableau d'entiers. L'adapter pour trier tout autre type dont les éléments sont comparables entre eux (chaîne de caractère, nombres décimaux, etc) devrait ensuite être plus facile.

Pour tester votre implémentation de l'algorithme, vous pouvez générer un tableau avec des éléments choisis aléatoirement, le trier avec la fonction sort de votre langage, puis comparer avec le tableau trié par votre implémentation. En kotlin, ça donnerait quelque chose comme suit :

fun quicksort(array: IntArray): IntArray {
    throw NotImplementedError("A implémenter")
}

fun generateRandomIntList(size: Int, min: Int = -1000, max: Int = 1000) =
    IntArray(size) { (min..max).random() }.toList()

fun generateRandomCharList(size: Int) = CharArray(size) { ('a'..'z').random() }.toList()

fun prettyPrintList(list: List<Any>) = println(list.joinToString(prefix = "[", postfix = "]"))

fun main() {
    // Int array
    val randomIntArray = generateRandomIntList(100)
    prettyPrintList(randomIntArray)

    val sortedIntArray = randomIntArray.sorted()
    prettyPrintList(sortedIntArray)

    val quickSortedIntArray = quicksort(randomIntArray)
    prettyPrintList(quickSortedIntArray)

    // Char array
    val randomCharArray = generateRandomCharList(100)
    prettyPrintList(randomCharArray)

    val sortedCharArray = randomCharArray.sorted()
    prettyPrintList(sortedCharArray)

    val quickSortedCharArray = quicksort(randomCharArray)
    prettyPrintList(quickSortedCharArray)
}

main()

Saurez-vous résoudre le problème ?

Bon courage !

Et sinon, voici une solution proposée par l'auteur en Kotlin :

fun <T : Comparable<T>> quicksort(array: List<T>): List<T> {
    if (array.isEmpty()) return emptyList()
    val pivot = array.last()
    val smallerValues = mutableListOf<T>()
    val equalValues = mutableListOf<T>()
    val biggerValues = mutableListOf<T>()
    array.forEach {
        when {
            it == pivot -> equalValues.add(it)
            it < pivot -> smallerValues.add(it)
            it > pivot -> biggerValues.add(it)
        }
    }
    return quicksort(smallerValues) + equalValues + quicksort(biggerValues)
}

Votre équipe TakiVeille