quicksort

Quicksort ist ein Sortieralgorithmus nach dem Prinzip „Teile und herrsche“. Rekursiv, Stück für Stück, analysieren wir das Zahlenarray, ordnen die Zahlen ausgehend vom ausgewählten Referenzelement in kleinerer und größerer Reihenfolge an und fügen das Referenzelement selbst in den Cutoff zwischen ihnen ein. Nach mehreren rekursiven Iterationen erhalten Sie eine sortierte Liste. Zeitkomplexität O(n²).

Schema:

Wir beginnen damit, eine Liste von Elementen von außen zu erhalten, die Sortiergrenzen. Im ersten Schritt werden die Sortiergrenzen von Anfang bis Ende festgelegt.
Überprüfen Sie, dass sich die Start- und Endgrenzen nicht überschneiden. Wenn dies passiert, ist es Zeit, den Vorgang abzuschließen
Wählen Sie ein Element aus der Liste aus und nennen Sie es Pivot
Bewegen Sie es am letzten Index nach rechts bis zum Ende, damit es nicht im Weg ist
Erstellen Sie einen Zähler mit *kleineren Zahlen*, die immer noch Null sind
Durchlaufen Sie die Liste von links nach rechts, bis einschließlich zum letzten Index, an dem sich das Referenzelement befindet
Wir vergleichen jedes Element mit dem Referenzelement
Wenn er kleiner als der Referenzwert ist, tauschen wir ihn entsprechend dem Index des Zählers kleinerer Zahlen aus. Erhöhen Sie den Zähler kleinerer Zahlen.
Wenn die Schleife das Stützelement erreicht, halten wir an und tauschen das Stützelement mit dem Element entsprechend dem Zähler der kleineren Zahlen aus.
Wir führen den Algorithmus separat für den kleineren linken Teil der Liste und separat für den größeren rechten Teil der Liste aus.
Infolgedessen werden alle rekursiven Iterationen aufgrund des Eincheckpunkts 2 angehalten
Erhalten Sie eine sortierte Liste

Quicksort wurde vom Wissenschaftler Charles Anthony Richard Hoare an der Moskauer Staatsuniversität erfunden. Nachdem er Russisch gelernt hatte, studierte er Computerübersetzung sowie Wahrscheinlichkeitstheorie an der Kolmogorov-Schule. 1960 verließ er aufgrund der politischen Krise die Sowjetunion.

Beispielimplementierung in 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);
  }
}

Wenn nichts klar ist, empfehle ich Ihnen, sich das Video von Rob Edwards von der University of San Diego anzusehen https://www.youtube.com/watch?v=ZHVk2blR45Q Es zeigt ganz einfach Schritt für Schritt das Wesen und die Implementierung des Algorithmus.

Links

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

Quellen