Что не так с моими векторами с рекурсивным слиянием? - PullRequest
Новая
       28

Что не так с моими векторами с рекурсивным слиянием?

0 голосов
/ 27 апреля 2019

Моя часть кода MergeSort выполнена, но есть некоторые проблемы сравнения и обмена. Мой temp вектор, который я настроил, копирует вектор для сортировки в мой temp вектор таким же образом. Например, мой вектор для сортировки будет v={5104, 8199, 123, 5678, 9999, 4356}, а затем в конце программы вектор temp будет установлен так же, как temp={5104, 8199, 123, 5678, 9999, 4356}. У меня есть все необходимые переменные, и мне сказали, что в методе outplaceMerge не должно быть циклов for, только операторы while и if / else. Я не собирался задавать этот вопрос, но я в растерянности. 

int main (int argc, char* argv[]) {
  //I have a method that makes the vector size its not shown 
  size_t n = vectorSize();
  vector<int> vect(n);

  std::random_device sd;
  std::mt19937 mt(sd());
  std::uniform_int_distribution<int> dist (0, 9999);

  for (size_t i = 0; i < n; ++i)
  {
      vect[i] = dist(mt);
  }
  mergeSort(vect);
  cout << "Merge time: " << ms << endl;
  vector<int> ACopy(vect);

  std::sort(ACopy.begin(), ACopy.end());
  if(vect == ACopy) {    
    cout << "Merge ok?     true" << endl;
  }else{
    cout << "Merge ok?      false" << endl;   
  }
  return EXIT_SUCCESS; 
}
/************************************************************/

size_t mergeSortH(vector<int>& v, vector<int>& temp, size_t first, size_t last) {   
    if (last - first > 1) {
        size_t mid = first+(last-first) / 2;
        mergeSortH(v, temp, first, mid);
        mergeSortH(v, temp, mid, last);
        outplaceMerge(v, temp, first, mid, last);
    }
//will return numCompares I just am waiting till I fix my sort
    return 0; 
}

/************************************************************/

size_t outplaceMerge(vector<int>& v, vector<int>& temp, size_t first, size_t mid, size_t last) {
  size_t numCompares = 0;
  size_t i1 = first;
  size_t i2 = mid;
  size_t i3 = first;

  while((v[first] < mid) && (v[first] < last)) {      
    if(v[first] < v[mid]) {
      temp[i3] = v[i1];
      ++i1;
    } else {
      temp[i3] = v[i2];
      ++i2;
    }    
    ++i3;
  }

  if(i1 > mid) {    
    while(i2 < last) {
      temp[i3] = v[i2];
      ++i2;
      ++i3;
    }   
  } else {
    while(i1 <= mid){
      temp[i3] = v[i1];
      ++i1;
      ++i3;    
    }
  }     
  cout << i3 << endl;  

  return numCompares;
}   
/************************************************************/

size_t mergeSort(vector<int>& v)
{
  vector<int> temp(v.size());
  return mergeSortH(v, temp, 0, v.size());
}

/************************************************************/

Вектор должен быть отсортирован от v={5104, 8199, 123, 5678, 9999, 4356} до temp={123, 4356, 5104, 5678, 8199, 9999} и поместить эти переменные обратно в исходный вектор v={123, 4356, 5104, 5678, 8199, 9999}. Выходных данных не требуется, его просто нужно отсортировать, и случайное число gen создает исходный вектор, поэтому эти значения являются лишь примером. Оператор Acopy сравнивается с сортировкой слияния после ее завершения, чтобы показать, отсортирована ли она. Если слияние = = Acopy, то возвращается true.

...