me

Mac1ek · 08-19-2024, 02:35 AM

Hello All. It is my implementation of merge sort algorithm in c++. I need opinion it is correct example:

Code:

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

template<typename T> std::vector<T>& merge(std::vector<T>& vec, typename std::vector<T>::size_type p, typename std::vector<T>::size_type q, typename std::vector<T>::size_type r) {

    std::vector<T> L(vec.begin()+p, vec.begin()+q);
    std::vector<T> R(vec.begin()+q, vec.begin()+r);
    typename std::vector<T>::size_type i = 0, j = 0, k = p;

    while(i < L.size() && j < R.size()) {
        if(L[i] < R[j]) {
            vec[k] = L[i];
            ++i;
        }
        else {
            vec[k] = R[j];
            ++j;
        }
        ++k;
    }

    while(R.begin()+j!=R.end()) {
        L.push_back(R[j]);
        ++j;
    }

    while(L.begin()+i!=L.end()) {
        vec[k] = L[i];
        ++k;
        ++i;
    }
    return vec;
}

template <typename T> std::vector<T>& merge_sort(std::vector<T>& vec, typename std::vector<T>::size_type p, typename std::vector<int>::size_type r) {

    if((r-p) < 2) {

        return vec;

    }
    auto q = ((p+r)/2);
    merge_sort(vec, p, q);
    merge_sort(vec, q, r);
    return merge(vec, p, q, r);

}

You can use them in main:

Code:

auto main() -> int {
        std::vector<int> vec({23432, 3454, 3, 33, 22, 1, 75});
        std::vector<int> result = merge_sort(vec, 0, 7);
        std::copy(result.begin(), result.end(), std::ostream_iterator<int>(std::cout, " "));
        return (0);
}

Any comment welcome.
Thanks for answer.

pan64 · 08-19-2024, 03:42 AM

in that case would be nice to change the title to something more appropriate, "me" is not really informative.
From the other hand would be nice to know if you have any issues with it? Can you use it? does it work perfectly, or is it just slow or crashing or what?
How did you build/compile it? Did you get any warning or error message?

But anyway, did you test it at all? Do you know if it is correct, don't you? Why did you ask it?

astrogeek · 08-19-2024, 04:50 PM

As already noted by pan64, an appropriate title would help you attract the attention of those most willing to offer help.

Also, as noted, are you having difficulties or trying to solve some problem? Does it work for you?

The more contextual information you provide, the better you help others help you!

Please review the Site FAQ for guidance in asking well formed questions. Especially visit the link from that page, How to Ask Questions the Smart Way for discussion of things to consider when asking others for help.

Good luck!

sundialsvcs · 08-22-2024, 06:17 PM

It really doesn't make much sense, frankly, to "ask for affirmation" about an algorithm that you've written. "Either it works, or seems to work, or it doesn't."

Develop the skills, yourself, to create tests which demonstrate that "your algorithm [implementation] works." And then, if they "pass," move along.

"In the real world," there will be no one to verify or "approve" your work, other than your co-workers. Who will be very annoyed if they find themselves "cleaning up after you."

NevemTeve · 08-23-2024, 04:33 AM

As a start, save a few bytes making your program more portable:

Code:

- auto main() -> int {
+ int main() {

Mac1ek · 08-23-2024, 05:38 AM

Im sorry I forget save topic title, I can change it now ?

Mac1ek · 08-23-2024, 05:39 AM

My question is about optimization merge sort algorithm in c++, based on my example.

sundialsvcs · 08-23-2024, 07:56 AM

Yes, I think that you can change the topic title in the original post. (Otherwise, "report" it, and thereby ask the site admins for help.) Please do try to do this, because your topic deserves to be discovered and right now it won't be.

Basically: create tests to determine if the algorithm appears to work. If it does, move along to something else. It is very unlikely that someone on a public forum is going to do a "code review" for you. Although you can certainly ask your co-workers (with the consent of your manager ...) to do such a thing. (On projects which I have managed, where "new algorithms" are being created, "code reviews" are mandated [by me].)

Finally: things like "merge sort" are usually handled by library routines of contributed code which have already been thoroughly tested by someone else. "Actum Ne Agas" – Do Not Do A Thing Already Done.

These days, no matter what it is you're doing, it is extremely likely that someone else has already done it, and has perfected it. Therefore, your task in nearly every case is not to code a brand-new solution, but to find what has already been well-done. Then, carefully incorporate it into your specific project. "We stand upon the shoulders of giants."

For instance, the Perl programming language's famous library, CPAN, today contains: "218,541 Perl modules in 45,287 distributions, written by 14,504 authors."

Literally, it includes modules about "ancient alphabets." Every single one of these modules perform a long series of automatic tests, on your system, before they will allow themselves to be installed. Every programming language these days has a similar resource. And, it's quite astonishing how big they are. "Here. Let me help you up ..."

boughtonp · 08-23-2024, 08:09 AM

Quote:

Originally Posted by Mac1ek

Im sorry I forget save topic title, I can change it now ?

Use the edit button on the first post of the thread.

astrogeek · 08-23-2024, 06:29 PM

Quote:

Originally Posted by Mac1ek

Im sorry I forget save topic title, I can change it now ?

Simply click the Edit button at bottom of the first post, click Go Advanced and change the title in the text edit box Title at top of the form.

Click Submit when done.