Проблема сортировки слиянием, передача массива между методами?

Я пишу программу, которая реализует быструю сортировку, сортировку вставкой и сортировку слиянием. Я могу заставить все работать, кроме сортировки слиянием, и я не могу понять, почему. Пожалуйста, игнорируйте переменные операции и сравнения. Они позволяют анализировать время выполнения и количество операций для разных входных файлов. Этот код запускается из основного через объект класса следующим образом:

Merge testobj13(test_Med[0], 100);
testobj13.merCall();
testobj13.display();

Для отсортированного списка класс сохраняет список отсортированным, для перевернутого списка список все еще остается в значительной степени перевернутым, за исключением первого и последнего значений, для рандомизированного списка я не вижу никакой схемы между выводом и исходным вводом. Я буду пытаться ответить на другие вопросы, пока я жду ответа. Любая критика приветствуется, даже если речь идет только о моем коде или синтаксисе, не относящихся к общей проблеме здесь. Я написал этот код на основе кода sudo, написанного моим классом алгоритмов, поэтому у меня возникли проблемы с обнаружением, что здесь не так.

# include <iostream>
# include <stdio.h>
# include <stdlib.h>

using namespace std;
class Merge{
public:
int comparisons, operations, middle, i, j, k, size;
int *myArray, *c;

Merge::~Merge(){
myArray = 0;
delete myArray;
}

Merge::Merge(int a [], int n) {
size= n;
myArray= new int[size];
comparisons = 0, operations = 0, middle = 0, i = 0, j = 0, k = 0;

for(int x = 0; x < size; x++){
myArray[x] = a[x];
}
}

void combine(int arr [], int first, int middle, int last){

i = first, j = middle + 1, k = first; operations = operations + 3;
c = new int[last + 1]; operations ++;

while( (i <= middle) && (j <= last) ){
comparisons++;operations++;
if(arr[i] <= arr[j]){operations++;
c[k] = arr[i]; operations++;
i++; operations++;
}
else{
c[k] = arr[j]; operations++;
j++; operations++;
}
k++; operations++;
}
while(i <= middle){operations++;
c[k] = arr[i]; operations++;
i++; operations++;
k++; operations++;
}
while(j <= last){operations++;
c[k] = arr[j]; operations++;
j++; operations++;
k++; operations++;
}
for(int k = first; k <= last; k++){operations++;
arr[k] = c[k]; operations++;
}
c = 0;
delete c;
}

void mer(int arr [], int first, int last){
operations++; //for the comparison in the following if statement
if ( first < last ){
middle = (first + last) / 2; operations++;
mer(arr, first, middle);  operations++;
mer(arr, middle + 1, last); operations++;
combine(arr, first, middle, last); operations++;
}
}

void merCall(){
mer(myArray, 0, size - 1);
}

void display(){

cout << "The array after going through Merge Sort: " ;

for(int x = 0; x < size; x++){
cout << endl << myArray[x];
}

cout << endl << "Number of operations :" << operations << "\t comparisons: " <<   comparisons << endl;

}};

3

Решение

Ваша «средняя» переменная перезаписывается во время рекурсии, потому что она является членом класса, а не локальной переменной:

middle = (first + last) / 2; operations++;

// This is going to affect middle
mer(arr, first, middle);  operations++;

// So this isn't going to work on the range you think it is.
mer(arr, middle + 1, last); operations++;

combine(arr, first, middle, last); operations++;

Было бы лучше объявить middle как локальную переменную:

int middle = (first + last) / 2; operations++;
mer(arr, first, middle);  operations++;
mer(arr, middle + 1, last); operations++;
combine(arr, first, middle, last); operations++;
1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]