Classificando uma matriz em C ++ usando Bubble sort

Question

Aqui está o meu algoritmo de classificação de bolhas que gostaria de melhorar de todas as formas possíveis

#include<iostream>

int main(){
    int arr[6] = {5,2,3,7,2,6};
    int f = 0;
    int b = 0;
    for(int i = 1;i < 6;i++){
        if(arr[i] < arr[i-1]){
            f = arr[i];
            b = arr[i-1];
            arr[i] = b;
            arr[i-1] = f;
            i=1;
        }

    }
    for(int i = 0;i < 6;i++) std::cout << arr[i] << " ";
}

Qualquer coisa é apreciada

Answer 1

Algumas notas:

• Eu evitaria executar um loop ao mudar por identro, isso não é muito claro para o leitor. Eu prefiro usar dois loops aninhados.
• A troca pode ser feita em uma etapa a menos
• Gostaria de inicializar uma variável de tamanho e usá-la em todo o código em vez de embutir em código 6.
• A impressão da matriz no console deve ser uma função separada (assim como a função de classificação, na verdade).

#include<iostream>

int main(){
    const int sz = 6;
    int arr[sz] = {5,2,3,7,2,6};
    do{
        swapped = false;
        for(int i = 1;i < sz; i++){
            if(arr[i] < arr[i-1]){
                int tmp = arr[i];
                arr[i] = arr[i-1];
                arr[i-1] = tmp;
                swapped = true;
            }
        }
    } while(swapped);
    print_array(arr, sz);
}

Answer 2

1. Está errado. Por exemplo, para a entrada {5,9,3,7,2,6}você imprime 5 2 3 6 7 9.
2. Não é um tipo de bolha. Mais como um tipo de inserção ineficiente.
3. Não é O (n ² ), mas apenas O (n ³ ). Por exemplo, para a entrada, int arr[100] = {99,98,97,...,2,1,0}você tem 161.799 iterações do seu loop (isso é 100C3 + 99).

Answer 3

Você não implementa a otimização óbvia para classificação por bolha. Se você percorrer o loop interno e nenhuma troca for feita, o array será classificado.

Isso reduz a complexidade do "Melhor caso" em O(n)vez da O(n^2)que você implementou.

---

Sua classificação é baseada em números inteiros. Isso não é muito útil em C ++, pois os arrays podem ser de quase tudo. Portanto, você deve pensar nisso como ser capaz de classificar uma lista de qualquer coisa.

Claro que você disse que eu apenas altero o tipo <int>para algo que eu quero e recompilo.

Claro, eu digo. Mas se você escolher um tipo Tgrande, seu código se tornará muito ineficaz porque você faz cópias do objeto no meio do loop.

    std::array<MyBigType>  arr;

            int tmp = arr[i];  // You made a copy of the object here.
            f = arr[i];        // You made a copy of the object here. 
            b = arr[i-1];      // You made a copy of another object here.

Portanto, cada vez que você está fazendo uma troca, você está fazendo três cópias do objeto.

Você pode fazer melhor usando std::move()para mover o objeto. Ou você pode usar std::swap()ou std::swap_iter()fazer um trabalho mais eficiente de mover objetos grandes.

---

Seu código assume que você está classificando um C-array. Em C ++, lidamos com as coisas de maneira diferente, abstraindo o contêiner nos referindo a coisas com iteradores. Dessa forma, podemos classificar qualquer tipo de contêiner, simplesmente fornecendo o iterador.

Agora, iteradores diferentes têm propriedades diferentes e você pode potencialmente otimizar o algoritmo pelo tipo de iterador que está usando.

---

Mais importante ainda, o código não funciona.
Você só tem um único loop. Você precisa de um loop aninhado (presumo que alguns

Você executa uma espécie de problema de copiar e colar! Presumi que não funcionou porque não entendi o hack que você fez para simular um segundo loop. Ainda está quebrado.

---

Está escrito de uma forma que dificulta a leitura.
O código é projetado para ser lido por humanos. Escreva o código de uma maneira que seja fácil de ler.

Answer 4

Eu sugeriria usar o material C ++ mais recente, pelo menos onde obviamente simplifica o código.

1. o

            int tmp = arr[i];
            arr[i] = arr[i-1];
            arr[i-1] = tmp;
   

pode ser escrito em uma linha em vez de três:

            std::swap(arr[i], arr[i-1]);

1. std::array é exatamente o mesmo que a matriz antiga, mas conhece o próprio tamanho:

            std::array<int,6> arr = {5,2,3,7,2,6};
   

e então você pode usar em arr.size()vez do 6 codificado permanentemente sobre o resto do código. Ao contrário std::vector, std::arrayé uma estrutura leve sem campos internos ou alocações de heap.

1. Para imprimir a matriz, o loop C ++ 11 é muito útil:

   for (auto a: arr) std::cout << a << " ";
   

Não tenho certeza, talvez pedir para usar iteradores seja demais, mas seria possível reescrever com iteradores:

  std::array<int,6> arr = {5, 2, 3, 7, 2, 6};

  static_assert(arr.size() >= 2);
  auto current = arr.begin();
  auto prev = current++;

  while (current != arr.end()) {
    if (*current < *prev) {
      std::swap(*current, *prev);
      current = arr.begin();
    }
    prev = current++;
  }

  for (int a: arr) std::cout << a << " ";

Este código seria benéfico ao classificar algo como std::dequeonde o acesso aleatório arr[i]não é tão eficiente. Este algoritmo só precisa de acesso imediato às posições atuais e anteriores. Vamos fazer desse seu lado forte.

static_assertque eu adicionei falharia em tempo de compilação, não em tempo de execução, se a matriz fosse muito pequena. O tamanho desta matriz é conhecido pelo compilador.