Início / coding / Perguntas / 76969012
Accepted
Daniel Yefimov
Asked: 2023-08-24 19:53:30 +0800 CST

Implementação de Merge Sort C++: não consigo encontrar erro na minha implementação

  • 772

Aqui está minha implementação de Merge Sort:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

using namespace std;


template <typename RandomIt>
void MergeSort(RandomIt range_begin, RandomIt range_end){

  int num_elements = distance(range_begin,range_end);
  if( num_elements < 2){
    return;
  }

  vector<typename RandomIt::value_type> v(range_begin, range_end);
  RandomIt mid_it = range_begin + num_elements/2;

  MergeSort(range_begin, mid_it);
  MergeSort(mid_it, range_end);

  for (int x : v) {
    cout << x << " ";
  }

  cout << endl;

  merge(begin(v), begin(v) + v.size()/2, begin(v) + v.size()/2, end(v), range_begin);


}

Suposição importante: é garantido que o comprimento do intervalo fornecido é uma potência de dois, portanto o vetor sempre pode ser dividido em duas partes iguais.

Quando executo a função int main() recebo o seguinte:

int main() {
  vector<int> v = {6, 4, 7, 6, 4, 4, 0, 1};
  MergeSort(begin(v), end(v));
  for (int x : v) {
    cout << x << " ";
  }
  cout << endl;
  return 0;
}

resultado: 4 4 0 1 6 4 7 6

A classificação não acontece e o algoritmo basicamente troca duas metades do vetor. Não consigo encontrar meu erro.

c++

2 respostas

  1. Best Answer

    Dentro da função é declarado um vetor local

    vector<typename RandomIt::value_type> v(range_begin, range_end);

    isso não está classificado. Ele é criado novamente a cada chamada recursiva da função.

    A única operação com este vetor não classificado na primeira chamada recursiva da função é a seguinte

    merge(begin(v), begin(v) + v.size()/2, begin(v) + v.size()/2, end(v), range_begin);

    Isso significa que o conteúdo do resultado do vetor original está sendo construído com base em seu conteúdo original utilizando esta operação na primeira chamada recursiva da função. Todas as chamadas recursivas subsequentes da função não influenciam o conteúdo do vetor local declarado na primeira chamada recursiva da função.

    O vetor local vé redundante. De qualquer forma, criar um novo vetor em cada chamada recursiva da função torna a função ineficiente. Você precisa usar std::inplace_mergecom o vetor original dentro da função.

    A função pode ter a seguinte aparência

    template <typename RandomIt>
void MergeSort( RandomIt range_begin, RandomIt range_end ) {

    auto num_elements = std::distance( range_begin, range_end );
    if ( notnum_elements < 2)
    {
        return;
    }

    RandomIt mid_it = std::next( range_begin, num_elements / 2 );

    MergeSort( range_begin, mid_it );
    MergeSort( mid_it, range_end );

    std::inplace_merge( range_begin, mid_it, range_end );
}

    Neste caso a saída do programa será

    0 1 4 4 4 6 6 7

    Ou se o compilador suportar C++ 17, a função pode ter a seguinte aparência

    template <typename RandomIt>
void MergeSort( RandomIt range_begin, RandomIt range_end ) 
{
    if ( auto num_elements = std::distance( range_begin, range_end ); not ( num_elements < 2 ))
    {
        RandomIt mid_it = std::next( range_begin, num_elements / 2 );

        MergeSort( range_begin, mid_it );
        MergeSort( mid_it, range_end );

        std::inplace_merge( range_begin, mid_it, range_end );
    }
}
    • 3

  2. Achei que a seguinte abordagem estava funcionando

    int range_length = distance(range_begin, range_end);
RandomIt mid = range_begin + range_length / 2;

vector<typename RandomIt::value_type> left(range_begin, mid);
vector<typename RandomIt::value_type> right(mid, range_end);

MergeSort(left.begin(), left.end());
MergeSort(right.begin(), right.end());

    O problema com o que você estava fazendo era que, ao mesclar as metades classificadas de 'v' de volta ao intervalo original, você não estava realmente modificando o intervalo original. Então, você está basicamente modificando o vetor local 'v'. Como resultado, os elementos classificados são armazenados em 'v', mas o intervalo original range_begin a range_end permanece inalterado

    • 0

relate perguntas