Classificação rápida

Quicksort é um algoritmo de classificação de divisão e conquista. Recursivamente, peça por peça, analisamos a matriz de números, colocando os números em ordem menor e maior a partir do elemento de referência selecionado, e inserimos o próprio elemento de referência no corte entre eles. Após várias iterações recursivas, você terá uma lista ordenada. Complexidade de tempo O(n²).

Esquema:

Começamos obtendo uma lista de elementos externos, os limites de classificação. Na primeira etapa, os limites de classificação serão do início ao fim.
Verifique se os limites inicial e final não se cruzam; se isso acontecer, é hora de terminar.
Selecione algum elemento da lista e chame-o de pivô
Mova-o para a direita até o final do último índice para que não atrapalhe
Crie um contador de *números menores* ainda iguais a zero
Percorrer a lista da esquerda para a direita, até e incluindo o último índice onde o elemento de referência está localizado
Comparamos cada elemento com o de referência
Se for menor que o de referência, trocamos de acordo com o índice do contador de números menores. Aumente o contador de números menores.
Quando o loop atinge o elemento de suporte, paramos e trocamos o elemento de suporte pelo elemento de acordo com o contador de números menores.
Executamos o algoritmo separadamente para a parte menor à esquerda da lista e separadamente para a parte maior à direita da lista.
Como resultado, todas as iterações recursivas começarão a parar devido à verificação no ponto 2
Obter uma lista ordenada

Quicksort foi inventado pelo cientista Charles Anthony Richard Hoare na Universidade Estadual de Moscou. Depois de aprender russo, ele estudou tradução computacional, bem como teoria das probabilidades na escola Kolmogorov. Em 1960, devido à crise política, deixou a União Soviética.

Exemplo de implementação em 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);
  }
}

Se nada estiver claro, sugiro assistir ao vídeo de Rob Edwards, da Universidade de San Diego https://www.youtube.com/watch?v=ZHVk2blR45Q mostra de maneira mais simples, passo a passo, a essência e a implementação do algoritmo.

Links

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

Fontes

Classificação rápida

Links

Fontes

Published by demensdeum

Leave a Comment