Tri rapide

Quicksort est un algorithme de tri diviser pour régner. De manière récursive, pièce par pièce, nous analysons le tableau de nombres, en plaçant les nombres dans un ordre de plus en plus grand à partir de l’élément de référence sélectionné, et insérons l’élément de référence lui-même dans la coupure entre eux. Après plusieurs itérations récursives, vous vous retrouverez avec une liste triée. Complexité temporelle O(n²).

Schéma :

Nous commençons par obtenir une liste d’éléments de l’extérieur, les limites de tri. Dans un premier temps, les limites de tri s’étendront du début à la fin.
Vérifiez que les limites de début et de fin ne se croisent pas ; si cela se produit, il est temps de terminer
Sélectionnez un élément dans la liste et appelez-le pivot
Déplacez-le vers la droite jusqu’à la fin du dernier index afin qu’il ne gêne pas
Créez un compteur de *nombres plus petits* toujours égaux à zéro
Parcourez la liste de gauche à droite, jusqu’au dernier index inclus où se trouve l’élément de référence
Nous comparons chaque élément avec celui de référence
S’il est inférieur à celui de référence, alors nous l’échangeons en fonction de l’index du compteur des nombres plus petits. Incrémentez le compteur des nombres plus petits.
Lorsque la boucle atteint l’élément de support, nous nous arrêtons et échangeons l’élément de support avec l’élément en fonction du compteur de nombres plus petits.
Nous exécutons l’algorithme séparément pour la plus petite partie gauche de la liste et séparément pour la plus grande partie droite de la liste.
Par conséquent, toutes les itérations récursives commenceront à s’arrêter en raison de l’enregistrement au point 2
Obtenir une liste triée

Quicksort a été inventé par le scientifique Charles Anthony Richard Hoare de l’Université d’État de Moscou. Ayant appris le russe, il a étudié la traduction informatique ainsi que la théorie des probabilités à l’école Kolmogorov. En 1960, en raison de la crise politique, il quitte l’Union soviétique.

Exemple d’implémentation dans Rust :


use rand::Rng;

fn swap(numbers: &mut [i64], from: usize, to: usize) {
    let temp = numbers[from];
    numbers[from] = numbers[to];
    numbers[to] = temp;
}

fn quicksort(numbers: &mut [i64], left: usize, right: usize) {
    if left >= right {
        return
    }
    let length = right - left;
    if length <= 1 {
        return
    }
    let pivot_index = left + (length / 2);
    let pivot = numbers[pivot_index];

    let last_index = right - 1;
    swap(numbers, pivot_index, last_index);

    let mut less_insert_index = left;

    for i in left..last_index {
        if numbers[i] < pivot {
            swap(numbers, i, less_insert_index);
            less_insert_index += 1;
        }
    }
    swap(numbers, last_index, less_insert_index);
    quicksort(numbers, left, less_insert_index);
    quicksort(numbers, less_insert_index + 1, right);
}

fn main() {
    let mut numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
    let mut reference_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

    let mut rng = rand::thread_rng();
    for i in 0..numbers.len() {
        numbers[i] = rng.gen_range(-10..10);
        reference_numbers[i] = numbers[i];
    }

    reference_numbers.sort();

  println!("Numbers           {:?}", numbers);
  let length = numbers.len();
  quicksort(&mut numbers, 0, length);
  println!("Numbers           {:?}", numbers);
  println!("Reference numbers {:?}", reference_numbers);

  if numbers != reference_numbers {
    println!("Validation failed");
    std::process::exit(1);
  }
  else {
    println!("Validation success!");
    std::process::exit(0);
  }
}

Si rien n’est clair, je vous suggère de regarder la vidéo de Rob Edwards de l’Université de San Diego https://www.youtube.com/watch?v=ZHVk2blR45Q il montre très simplement, étape par étape, l’essence et la mise en œuvre de l’algorithme.

Liens

https://gitlab.com/demensdeum /algorithms/-/tree/master/sortAlgorithms/quickSort

Sources

Tri rapide

Liens

Sources

Published by demensdeum

Leave a Comment