Help with mergesort with a random vector!

Question

1.00/5 (1 vote)

See more:

so far I have this as my code

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

void merge(vector<int> aVector, int size, int low, int middle, int high){
    int temp[size];
    for(int i = low; i <= high; i++){
        temp[i] = aVector[i];
    }
    int i = low;
    int j = middle+1;
    int k = low;

    while (i <= middle && j <= high){
        if(temp[i] <= temp[j]){
            aVector[k] = temp[i];
            ++i;
        }
        else {
            aVector[k] = temp[j];
            ++j;
        }
        ++k;
    }
    while (i <= middle){
        aVector[k] = temp[i];
        ++k;
        ++i;
    }
}

void mergeSort(vector<int> aVector, int size, int low, int high){
    if (low < high){
        int middle = (low + high) / 2;
        mergeSort(aVector, size, low, middle);
        mergeSort(aVector, size, middle+1, high);
        merge(aVector, size, low, middle, high);
    }
}
int main()
{
    const int size = 10;
	vector<int> aVector;
	srand((unsigned)time(NULL));
	for (int i = 0; i < 10; i++) {
		int b = rand() % 9 + 1;
		aVector.push_back(b);
        cout << aVector[i] << " ";
        mergeSort(aVector, size, 0, 10);
	}
	return 0;
}

I only half understand mergeSort and not enough to do it with a randomized vector. So this code makes the .exe stop working is there a part I can fix or do I have to approach this in a different angle?

What I have tried:

I've tried googling and going through many different examples of mergeSort but none of them really work with vectors and the few that do have very simple already set vectors. I can't find one for a randomized vector.

Posted 26-Feb-16 16:37pm

Unicow

Updated 27-Feb-16 2:08am

Add a Solution

Comments

Sergey Alexandrovich Kryukov 27-Feb-16 1:03am

Software is written not by finding a solution, but by writing software using developer's brain.
—SA

Richard MacCutchan 27-Feb-16 4:19am

The principle of merge sorting is the same whatever the source data. The only part you need to change is the place where it needs to examine the data to decide the order of the elements.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

nv3 · Answer 1 · 2016-02-27T00:17:00

Okay, you have written some code and it doesn't do what you want or - as in your case - doesn't even compile. In this case you need to run your program in a debugger or understand the error messages the compiler is giving you. That is not easy when you are doing it the first time, but it will become easier with some practice. Googling for others that ran into the same trouble will not help you.

That said, let's start systematically. First start be re-reading your course notes and understanding them FULLY. You might even get a wider perspective by reading articles like this one Merge sort - Wikipedia, the free encyclopedia[^].

I won't do the work for you, as this is certainly an exercise and you should learn by doing it. But I am going to give you a couple of hints:

C++

void merge(vector<int> aVector, int size, int low, int middle, int high)
</int>

The size argument is actually superfluous. aVector can tell you its size by the size() member function. By passing the size a second time gives only room to make mistakes.

C++

{
    int temp[size];

This will not work. It won't even compile. And it certainly is not very efficient. If you need a temporary array (and you do for the merge sort algorithm), better allocate it once in your mergeSort function and pass it to every call of merge. You may use another vector<int> for the temporary array.

C++

int middle = (low + high) / 2;
mergeSort(aVector, size, low, middle);
mergeSort(aVector, size, middle+1, high);

Use the same conventions throughout your program. You started by defining low as the first element of the range and high as the first element beyond the range. That is a very common practice in C / C++. Now look at your definition of middle: The first call to mergeSort will sort that range from low up to and not including middle. You see where you made a mistake?

Take a look at all of your loops and check whether they should up and including or excluding the final value, i.e. whether you need to compare with <= or <. Double check each and every loop!

Run your program in a debugger and stop at every single statement. Check whether your program did exactly what you expected it to do by looking at the variables.

I hope these hints will get you on the right way.

Patrice T · Answer 2 · 2016-02-27T02:08:00

When programming, the first step is to understand what you program.
Merge sort - Wikipedia, the free encyclopedia[^]
look at the graphics.

Randomized vector is just a vector with values that you don't know. where is the difficulty ?

Obviously, your own code is like a blackbox to you. It don't do what you expect, and you don't understand why.
What follow is not directly a solution to your problem, but a key that will help you to understand by yourself what is wrong.
The debugger is your friend. It will show you what your code is really doing.
Follow the execution, inspect variables and you will see that there is a point where it stop doing what you expect.
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]

Advices:
- you can put comments in your code.

- be consistent!
in first call, 10 is last row+1, do the same everywhere !

C++

mergeSort(aVector, size, 0, 10);

C++

mergeSort(aVector, size, low, middle);
mergeSort(aVector, size, middle +1, high);

You need to study C++ arrays and understand that the first row is 0 and last row is size-1.

It is only a few problems you have.
My advice: run the program line by line on debugger inspect variables changes on every step and you will see where it don't behave as expected.

Help with mergesort with a random vector!

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0