-2

I'm very new to C++ and only coded in python before, but python is too slow for my purposes now. I did a mergesort algorithm in python and it worked. But now I translated it into C++ and I got a bunch of errors in my IDE. What are my errors?

#include <iostream>

using namespace std;

int *sort(int lenght, int lis[]) {
    int units = lenght;
    int umt;
    int tiles = 1;
    while (units > 1) {
        bool whole = true;
        umt = units % 2;
        if (umt = 1) {
            units++;
            whole = false;
        }
        units = units / 2;
        tiles = tiles * 2;
        if (whole) {
            int buffd[units];
            int add_l = 0;
            int add_r = 0;
            int prod_l = 0;
            int prod_r = prod_l + tiles / 2;
            for (int k = 0; k < units; k++) {
                int buffd[units];
                int add_l = 0;
                int add_r = 0;
                int prod_l = k * tiles;
                int prod_r = prod_l + tiles / 2;
                for (int f = 0; f < tiles; f++) {
                    if (lis[prod_l + add_l] <= lis[prod_r + add_r]) {
                        buffd[f] = lis[prod_l + add_l];
                        add_l++;
                        if (add_l = tiles / 2) {
                            for (int e = f; e < tiles; e++) {
                                buffd[e] = lis[prod_r + add_r + e];
                            }
                            f = tiles;
                        }
                    } else {
                        buffd[f] = lis[prod_r + add_r];
                        add_r++;
                        if (add_r = tiles / 2) {
                            for (int e = f; e < tiles; e++) {
                                buffd[e] = lis[prod_l + add_l + e];
                            }
                            f = tiles;
                        }
                    }
                }
                for (int i = prod_l; i < prod_l + tiles; i++) {
                    lis[i] = buffd[i - prod_l];
                }
            }
        } else {
            int buffd[units];
            int add_l = 0;
            int add_r = 0;
            int prod_l = 0;
            int prod_r = prod_l + tiles / 2;
            for (int k = 0; k < units - 1; k++) {
                int buffd[units];
                int add_l = 0;
                int add_r = 0;
                int prod_l = k * tiles;
                int prod_r = prod_l + tiles / 2;
                for (int f = 0; f < tiles; f++) {
                    if (lis[prod_l + add_l] <= lis[prod_r + add_r]) {
                        buffd[f] = lis[prod_l + add_l];
                        add_l++;
                        if (add_l = tiles / 2) {
                            for (int e = f; e < tiles; e++) {
                                buffd[e] = lis[prod_r + add_r + e];
                            }
                            f = tiles;
                        }
                    } else {
                        buffd[f] = lis[prod_r + add_r];
                        add_r++;
                        if (add_r = tiles / 2) {
                            for (int e = f; e < tiles; e++) {
                                buffd[e] = lis[prod_l + add_l + e];
                            }
                            f = tiles;
                        }
                    }
                }
            }
            for (int i = prod_l; i < prod_l + tiles; i++) {
                lis[i] = buffd[i - prod_l];
            }
        }
    }
    return lis;
}

int main() {
    int to_sort[8] = { 23, 1, 654, 2, 4, 87, 3, 1 };
    cout << "sortiert: ";
    int *sorted;
    sorted = sort(8, to_sort);
    for (int p = 0; p < 8; p++) {
        cout << sorted[p] << " ";
    }
    return 0;
}

The errors are in German and I have no idea why, the rest of the IDE is in English. Does anyone know how to set that to English, I'm using Clion from JetBrains.

chqrlie
  • 131,814
  • 10
  • 121
  • 189
kamelfanger83
  • 97
  • 1
  • 7
  • 2
    _"I just had to have more text:"_ Don't do that. The engine doesn't let you post for a reason! – πάντα ῥεῖ Nov 27 '20 at 17:47
  • 4
    One of errors looks like your usage of `=` in the `if` statements. – MikeCAT Nov 27 '20 at 17:48
  • merge sort is recursive. If you have a non-recursive merge sort, cool beans, but it's not merge sort anymore. Instead of posting filler, post more information. For example, like expand on *i got a bunch of errors in my IDE*. Odds are good someone will see the error messages and damn near instantly be able to answer the question. Good questions save time. A lot of the time a good question eliminates the need to ask the question. – user4581301 Nov 27 '20 at 18:05
  • 1
    Side note: About the only thing Python and C++ have in common is they are both programming languages. Don't program C++ the way you would python or you will get even worse results than you had in python. In order to get the speed that C++ can offer, you have to write C++ code using C++'s idioms and best practices. – user4581301 Nov 27 '20 at 18:07
  • 3
    `int buffd [units];` is a variable length array. These aren't [valid in Standard C++](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). Some compilers allow them, but they're a great way to overflow a stack. Also note you define four variables named `buffd` they are different variables. What you do with one does NOT magically affect the other. – user4581301 Nov 27 '20 at 18:12
  • 1
    You are declaring the same variable after the `if` and inside the `for`. Why? They will be different copies. – Thomas Matthews Nov 27 '20 at 18:51
  • 1
    Let's start with the basics. If you want a fast sort algorithm, don't write your own, use a library. – n. m. could be an AI Nov 27 '20 at 19:36
  • @MikeCAT okay thanks i fixed that – kamelfanger83 Nov 27 '20 at 19:51

1 Answers1

2

There are some major problems in your code:

  • comparisons must use == instead of =, which is the assignment operator.
  • the redundant definitions for buffd, add_l, add_r, prod_l and prod_r should me removed.
  • variable length array definitions such as int buffd[units] are not supported by many C++ compilers. These are extensions for compatibility with C90 optional features, likely to cause stack overflow for large arrays. You should allocate these arrays or use std::vector.
  • these local arrays are declared with a incorrect size: it should be int buffd[tiles];, not int buffd[units]. Undefined behavior ensues.
  • the last for loop is outside the body of the previous loop, which is incorrect.
  • you do not increment f before copying the remaining elements from the other slice when either add_l or add_r equals tiles / 2.
  • your non-recursive algorithm cannot succeed in the general case, I got it to work for array lengths that are powers of 2, and it is quite surprising that it may come as a translation from your python version. There are much simpler ways to program mergesort in python, and in C++ too.

With some extra work, I simplified your code and got it to work for the general case:

#include <iostream>

using namespace std;

int *sort(int length, int lis[]) {
    for (int tile = 1; tile < length; tile += tile) {
        int tiles = tile + tile;
        int *buffd = new int[tiles];
        for (int prod_l = 0; prod_l < length; prod_l += tiles) {
            int add_l = 0;
            int max_l = tile;
            int add_r = 0;
            int max_r = tile;
            int prod_r = prod_l + max_l;
            int f = 0;
            if (prod_r >= length)
                break;
            if (prod_r + max_r > length)
                max_r = length - prod_r;
            for (;;) {
                if (lis[prod_l + add_l] <= lis[prod_r + add_r]) {
                    buffd[f++] = lis[prod_l + add_l++];
                    if (add_l == max_l) {
                        while (add_r < max_r) {
                            buffd[f++] = lis[prod_r + add_r++];
                        }
                        break;
                    }
                } else {
                    buffd[f++] = lis[prod_r + add_r++];
                    if (add_r == max_r) {
                        while (add_l < max_l) {
                            buffd[f++] = lis[prod_l + add_l++];
                        }
                        break;
                    }
                }
            }
            for (int i = 0; i < f; i++) {
                lis[prod_l + i] = buffd[i];
            }
        }
        delete[] buffd;
    }
    return lis;
}

int main() {
    int to_sort[8] = { 23, 1, 654, 2, 4, 87, 3, 1 };
    for (int i = 1; i < 8; i++) {
        cout << "sortiert: ";
        int *sorted = sort(i, to_sort);
        for (int p = 0; p < i; p++) {
            cout << sorted[p] << " ";
        }
        cout << endl;
    }
    return 0;
}

Here is a classic top-down recursive implementation for reference:

void mergesort(int lis[], int lo, int hi, int *tmp) {
    if (hi - lo >= 2) {
        int mid = (hi - lo) / 2;
        mergesort(lis, lo, lo + mid, tmp);
        mergesort(lis, lo + mid, hi, tmp);
        for (int i = 0; i < mid; i++)
            tmp[i] = lis[lo + i];
        for (int i = 0, j = lo + mid, k = lo; i < mid;) {
            if (j >= hi || tmp[i] <= lis[j])
                lis[k++] = tmp[i++];
            else
                lis[k++] = lis[j++];
        }
    }
}

int *mergesort(int length, int lis[]) {
    int *tmp = new int[length / 2];
    mergesort(lis, 0, length, tmp);
    delete[] tmp;
    return lis;
}
chqrlie
  • 131,814
  • 10
  • 121
  • 189
  • thanks for your tips 1 and 2. tip number 3: what do i have to use instead if I want a array with as many elements as units and that is called buffd? and also: why do you all think my programm is non-recursive? i have a while loop and i also have several for loops and the programm worked in python with exactly this many loops. also: what are theese much simpler ways to program mergesort? – kamelfanger83 Nov 27 '20 at 20:04
  • Your algorithm is non recursive because the function `mergesort` does not call itself recursively. You implemented a bottom-up iterative `mergesort` that is not adequate for all sizes. You probably have the same issues in your python code. – chqrlie Nov 27 '20 at 20:09
  • @kamelfanger83 if you need an array and don't know the size, start with [`std::vector`](https://en.cppreference.com/w/cpp/container/vector). If that's not allowed for some reason, the you've got material for at least one more question. Fortunately it's been asked a bunch of times already so you should be able to find help in existing SO questions. – user4581301 Nov 27 '20 at 20:11
  • thank you very much!!! I still have a few questions: why is this code recursive and mine wasn‘t? What does the for(;;) do? But thanks a lot for the rest, helped me a lot to better understand C++. <3 – kamelfanger83 Nov 27 '20 at 23:52
  • @kamelfanger83: this code is not recursive either. `for(;;)` is a for ever loop, it keeps iterating until explicitly broken from with a `break` or `return` statement. Equivalent to `while(true)` – chqrlie Nov 28 '20 at 11:30
  • @chqrlie ok, so why did everybody say that the algorithm has to be recursive? – kamelfanger83 Nov 28 '20 at 13:12
  • @kamelfanger83: not everyone did, user4581301 insisted that mergesort had to be recursive to deserve the name, which is incorrect. Mergesort can be implemented top-down in a recursive fashion or bottom-up with different methods. Your version is not very efficient cache-wise and suboptimal for array sizes not powers of 2, but it definitely qualifies as a merge sort variant. – chqrlie Nov 28 '20 at 15:50
  • @chqrlie ok do have any links or sth to a better mergesort algorithm on stack overflow or somewhere? – kamelfanger83 Nov 29 '20 at 14:42
  • @kamelfanger83: I posted a recursive implementation in the answer. You can learn more about this and other algorithms from the Wikipedia: https://en.wikipedia.org/wiki/Merge_sort – chqrlie Nov 29 '20 at 18:06