How do i make this sorting algorythm work?

Question

Im trying to experiment with some iterative sorting algorythms, im trying hard to make this one work. It is actually fine when i use it on small lists of 20 or less, but when i go up to 200 or more elements it gives me a runtime error (exception not handled). I guess it's a memory problem, but i dont really know how to proceed.

The result that i would like to get is a function that takes a list, splits it in two part depending if the elements are bigger or smaller than the average. Then the function is called again on both the new lists created. When it takes a list that is either empty, with a single element, or already sorted, it should do nothing.

The error: Unhandled exception at 0x00007FFF05EE5469 (ucrtbased.dll) in ConsoleApplication4.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x000000B0AB403FF8).

#include <list>
#include <iostream>

void mySort(std::list<int>& input_list) {

    if (input_list.begin() != input_list.end()) {
        
        std::list<int> listaMin;
        std::list<int> listaMaj;
        std::list<int>::iterator it;
        bool alreadySorted = true;
        int previousValue = 0;
        int avg = 0, counter = 0;


        for (it = input_list.begin(); it != input_list.end(); it++) {
            
            if (*it >= previousValue)previousValue = *it;
            else alreadySorted = false;
            avg += *it;
            counter++;
        }
        
        if (alreadySorted == false) {

            for (it = input_list.begin(); it != input_list.end(); it++) {
                
                if (*it < (avg / counter)) { listaMin.push_front(*it); }
                else listaMaj.push_front(*it);
            }

            mySort(listaMin);
            mySort(listaMaj);

            input_list.clear();
            input_list.merge(listaMaj);
            input_list.merge(listaMin);

        }
    }
}

Later:

int main() {

    srand(time(NULL));
    std::list<int> mainList;
    for (int i = 0; i < 100; i++) mainList.push_back(rand() % 100);

    mySort(mainList);

    return 0;
}

You are getting a Stack Overflow, which happens because likely your call stack is getting to big. This can happen when using recursion (incorrectly) as you are here. See [Wikipedia](https://en.wikipedia.org/wiki/Stack_overflow). — Mushroomator, Mar 23 '22 at 12:32
Trace - on paper or [in a debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) - what your function does when called with the list `{ 1, 0 }`. You will find that the function eventually calls the function again with the list `{ 1, 0 }`. — Drew Dormann, Mar 23 '22 at 12:35
@SamVarshavchik I don't know which of us noticed that first. :) Thanks though. — Drew Dormann, Mar 23 '22 at 12:37
Should i write then an option for this specific case? (`{ 1, 0 }`) or there is a smarter way around? — Ceccoclat, Mar 23 '22 at 12:46
@Ceccoclat `{ 1, 0 }` is not a _unique case_, it's just a simple case that illustrates that your function can call itself again with the same list it was passed. Which means it will recurse infinitely. When you call `mysort` on `listaMin` and `listaMax`, you should recognize that if one of those lists is empty, you have a problem. — Drew Dormann, Mar 23 '22 at 12:52
@Ceccoclat *a function that takes a list, splits it in two part depending if the elements are bigger or smaller than the average.* -- `auto iter = std::partition(input_list.begin(), input_list.end(), [&](int n) {return n < avg; });` -- That does all the work you're trying to do now with splitting the list on a particular value. You don't even need to create two lists, as `iter` in that small code snippet tells you where the partition is. — PaulMcKenzie, Mar 23 '22 at 12:59
@Ceccoclat [std::partition](https://en.cppreference.com/w/cpp/algorithm/partition) and [std::stable_partition](https://en.cppreference.com/w/cpp/algorithm/stable_partition). — PaulMcKenzie, Mar 23 '22 at 13:03
I removed your request for code review feedback. You might want to take a look at [the codereview.stackexchange.com guidelines](https://codereview.meta.stackexchange.com/q/5777) to see if your question _later_ fits there instead. — starball, Dec 18 '22 at 23:41

score 1 · Accepted Answer · answered Mar 23 '22 at 12:45

Your problem is that you are using integer division in calculating the average used to split your list into 2 parts.

Consider elements a list of 3 elements { 1, 2, 1 }. This results in avg = 4 and counter = 3.

You then split the list into two depending on whether each element is < or >= avg / counter.

In this case, avg / counter = 4 / 3 = 1 (using integer division)

With all 3 elements being >= 1, you end up with listaMaj containing all 3 elements and listaMin containing 0.

The call to mysort(listaMaj) then results in infinite recursion as the same list is effectively passed on unchanged forever.

Defining your avg variable as double instead of int, would fix this.

@Ceccoclat If this answers your question, don't forget to mark it as an answer. — Lrrr, Mar 23 '22 at 15:20

How do i make this sorting algorythm work?

1 Answers1