Сортировка двух массивов в объединенный массив

Во-первых, есть некоторые непосредственные проблемы с тем, как вы используете C ++:

• Ты используешь = вместо == для проверки на равенство (следовательно, вызывающие нежелательные присваивания значения и условие if возвращают true, когда это не должно);
• Ваша внешняя петля верхняя граница определяется как i <= 10в то время как правильная проверка границ будет i < 10;
• У вас есть утечка памяти в конце функции, потому что вы не можете отменить выделение памяти. Тебе необходимо delete [] combinedArray в конце.

Во-вторых, ваш внешний цикл перебирает все значения массива назначения, и на каждом этапе использует внутренний цикл для перебора всех значений исходных массивов. Это не то, что вы хотите. Что вы хотите одна петля считая от j=0 в j<5 и итерации по исходным массивам. Позиции в массиве назначения затем определяются как 2*j а также 2*j+1и нет необходимости во внутреннем цикле.

В-третьих, как объясняется в комментарии, для правильной реализации слияния отсортированных списков необходимы два независимых счетчика. j1 а также j2, Тем не менее, ваш текущий ввод встроен в код, и если вы замените 00 с 100Ваш текущий алгоритм (после внесения вышеуказанных исправлений) будет фактически работать для данного входа.

Наконец, что не менее важно, мне интересно, почему ваш целевой массив размещается в куче, используя new, Пока вы имеете дело с небольшими массивами, вы можете размещать их в стеке так же, как исходные массивы. Однако, если вы размещаете его в куче, лучше использовать std::unique_ptr<>возможно в сочетании с std::array<>, Вы получите бесплатное распределение ресурсов, не думая о delete [] заявление в конце функции.

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

int a[] = { 1, 2, 3 };
int b[] = { 4, 5, 6 };

Если вы хотите отсортировать результат, то первые три элемента приходят из первого массива. Имея это в виду, подумайте о том, что вы действительно знаете о данных. В частности, оба массива отсортированы, что означает, что первые элементы будут меньше, чем остальные элементы в соответствующем массиве. Смысл этого в том, что чем меньше элемент, тем меньше головы. Поместив этот элемент в результат, вы уменьшили проблему до меньшего множества. У тебя есть a' = { 2, 3 }, b = { 4, 5, 6 } а также res = { 1 } и новая проблема, которая находит второй элемент res знаю это a' а также b отсортированы.

Выясните на бумаге, что вам нужно сделать, тогда вам должно быть просто сопоставить это с кодом.

Итак, я изменил ваш код, чтобы он работал. На самом деле было бы неплохо иметь два указателя / индекса для двух отсортированных массивов. Так что вы можете обновить свой соответствующий указатель после добавления его в комбинированный массив. Дайте мне знать, если вы не понимаете какую-либо часть этого кода. Благодарю.

    int sortedArray1 [5] = {11, 33, 55, 77, 99};
int sortedArray2 [5] = {0, 22, 44, 66, 88};
int combinedSize = 10;
int *combinedArray;
combinedArray = new int[combinedSize];
int j = 0;
int k = 0;
for(int i = 0; i < combinedSize; i++)
{
if (j < 5 && k < 5) {
if (sortedArray1[j] < sortedArray2[k]) {
combinedArray[i] = sortedArray1[j];
j++;
} else {
combinedArray[i] = sortedArray2[k];
k++;
}
}
else if (j < 5) {
combinedArray[i] = sortedArray1[j];
j++;
}
else {
combinedArray[i] = sortedArray2[k];
k++;
}
}

for(int i = 0; i < combinedSize; i++)
{
cout << combinedArray[i];
cout << " ";
}
cout<<endl;

else if(sortedArray1[j] = sortedArray2[j]), ты имел ввиду else if(sortedArray1[j] == sortedArray2[j])?

Первый из них назначит значение sortedArray2 [j] для sortedArray1 [j] — и именно поэтому вы получаете 5 77 5 77...

Но где же 5 родом из? Там нет 5 в любом sortedArrayпока не нахожу for(int j = 0; j <= 5; j++) должно быть что-то не так. Самый высокий показатель размера N массив N-1 скорее, чем N в C / C ++ (но не в Basic) .. так что используйте j<5 как условие, или вы можете попасть в какую-то ситуацию, которую трудно объяснить или предсказать.

В конце концов, есть проблема в самом вашем алгоритме, каждый раз, когда внешний цикл зацикливается, он, наконец, сравнивает последние элементы в двух массивах, что приводит к тому, что вывод повторяет два числа.

Так что вам нужно исправить свой алгоритм тоже, смотрите Сортировка слиянием.

Немного другой подход, который ИМХО немного чище:

//A is the first array, m its length
//B is the second array, n its length
printSortedAndMerged(int A[], int m, int B[], int n){
int c[n+m];
int i=0, j=0;

for(int k=0; k < n+m; k++){

if(i < m && j < n){
if(A[i] < B[j]){
c[k] = A[i];
i++;
}
else{
c[k] = B[j];
j++;
}
continue; //jump to next iteration
}

if(i < m){ // && ~(j < n)
//we already completely traversed B[]
c[k] = A[i];
i++;
continue;
}

if(j < n){ // %% ~(i < m)
//we already completely traversed A[]
c[k] = B[j];
j++;
continue;
}

//we should never reach this
cout << "Wow, something wrong happened!" << endl;
}//for

for(int i=0; i<n+m; i++){
cout << c[i] << endl;
}
}

Надеюсь, поможет.