1

Okay I have fiddled around with everything and can not find the problem. I am new to c++ and really need help with this. The merge sort works perfectly but for some odd reason will not give all the values. Working with recursive merge sort can be confusing so was hoping I could have this problem solved. Thank you!1

the output when program is ran. ignore the bubble sort: the output when program is ran. ignore the bubble sort

Here is the input from the image: {41, 18467, 6334, 26500, 19169, 15724, 11478, 29358, 26962, 24464, 5705, 28145, 23281, 16827, 9961, 491, 2995, 11942, 4827, 5436}

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector <int> mergeSort(vector <int> data);

vector <int> merge(vector <int> arrayOne, vector <int> arrayTwo);

vector <int> dataList;

vector <int> dataListSorted;

int main()
{
    for (int i = 0; i < 20; i++)
    {
        dataList.push_back(rand());
    }

    int arrSize = dataList.size();
    cout << arrSize << endl;

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


    dataListSorted = mergeSort(dataList);

    cout << "mergeSort" << endl;

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


vector <int> mergeSort(vector <int> data)
{
    int arrSize = data.size();

    if (arrSize == 1)
    {
        return data;
    }

    vector <int> arrayOne;
    vector <int> arrayTwo;
    
    for (int i = 0; i < (arrSize / 2); i++)
    {
        arrayOne.push_back(data[i]);
        arrayTwo.push_back(data[i+arrSize/2]);
    }

    arrayOne = mergeSort(arrayOne);
    arrayTwo = mergeSort(arrayTwo);

   
    return merge(arrayOne,arrayTwo);
}
   
vector <int> merge(vector <int> arrayOne, vector <int> arrayTwo)
{
    vector <int> data;

    
    while (arrayOne.size() != 0 && arrayTwo.size() != 0)
    {
        if (arrayOne[0] > arrayTwo[0])
        {
            data.push_back(arrayTwo[0]);
            arrayTwo.erase(arrayTwo.begin());
        }
        else
        {
            data.push_back(arrayOne[0]);
            arrayOne.erase(arrayOne.begin());
        }
    }

    while (arrayTwo.size() != 0)
    {
        data.push_back(arrayTwo[0]);
        arrayTwo.erase(arrayTwo.begin());
    }
    while (arrayOne.size() !=  0)
    {
        data.push_back(arrayOne[0]);
        arrayOne.erase(arrayOne.begin());
    }

    return data;
    

    
}
Zain siu
  • 13
  • 3
  • Please edit your post with the input as text. My computer tools aren't set up to extract the numbers from the image, nor am I willing to hook up a projector to the computer to see the numbers. – Thomas Matthews Apr 23 '21 at 23:57
  • @ThomasMatthews The input is random but I will edit it to include the numbers shown, – Zain siu Apr 24 '21 at 00:01
  • My friend, you have a strange definition of "working" if it includes sorts deleting data. – user4581301 Apr 24 '21 at 00:39

1 Answers1

0

The loop

for (int i = 0; i < (arrSize / 2); i++)
{
    arrayOne.push_back(data[i]);
    arrayTwo.push_back(data[i+arrSize/2]);
}

fails to work correctly when arrSize is an odd number. For example, if arrSize is 5, then arrSize / 2 evaluates to 2. Then, i takes values 0 and 1. So, arrayOne covers indices 0 and 1, and arrayTwo covers indices 0+2=2 and 1+2=3. Index 4 gets missed.

You could fix it by adding a conditional check, or using two loops. For example, you could add, after the loop

if (arrSize % 2 == 1) {
    arrayTwo.push_back(data[arrSize-1]);
}

Even better, you could slice the array. That is, you could remove the loop and use:

arrayOne = vector<int>(data.begin(), data.begin()+arrSize/2);
arrayTwo = vector<int>(data.begin()+arrSize/2, data.end());
GoodDeeds
  • 7,956
  • 5
  • 34
  • 61