CODEWITHSUNDEEP
c++sortingstl
Ceccoclat
Ceccoclat

Reputation: 113

How do i make this sorting algorythm work?

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;
}

Upvotes: 0

Views: 83

Answers (1)

Ian Cook
Ian Cook

Reputation: 1196

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.

Upvotes: 1

Related Questions