CODEWITHSUNDEEP
c++sortingstdvector
Xuuuc
Xuuuc

Reputation: 31

Ascending sort, c++, with vectors

I am trying to make a sort function for std::vector, but I have a problem with negative values. I don't want to use function vector::sort. Queue is a vector.

My input :

1, -2, -241, 332, 2667, -2667, 266217, 2667, 13, -22, -41, 2332

Output :

266217, 2667, 2667, 2332, 332, 13, 1, -2. -241, -2667, -22, -41

Basically everything works, and then it crashes from unclear reasons for me.

Function :

void PriorityQueue::Push(double value)
{
    std::vector<double>::iterator pr;

    if (Queue.empty())
    {
        Queue.push_back(value);
    }

    else if (!Queue.empty())
    {
        for (pr = Queue.begin(); pr != Queue.end(); pr++)
        {
            if (value > *pr || value == *pr)
            {
                Queue.insert(pr, value);
                break;
            }

            else if (value < 0)
            {
                if (value > *pr || value == *pr)
                {
                    Queue.insert(pr, value);
                    break;
                }

                else if (value < *pr)
                {
                    Queue.push_back(value);
                    break;
                }
            }
        }
    }
}

Upvotes: 3

Views: 205

Answers (2)

selbie
selbie

Reputation: 104569

I'm fairly certain, based on the hints you've given in your comments, this is what you want. It doesn't need to treat the empty list or negative numbers special. And if value doesn't get inserted within the for loop, it's assumed to be at the end.

void PriorityQueue::Push(double value)
{
    bool inserted = false;

    for (auto pr = Queue.begin(); pr != Queue.end(); pr++)
    {
        if (value >= *pr)
        {
            Queue.insert(pr, value);
            inserted = true;
            break;
        }
    }
    if (inserted == false) // handle the case of inserting a number at the end
    {
        Queue.push_back(value);
    }
}

This will reliably insert elements in descending order without having any special need to treat negative numbers special.

Upvotes: 1

Serge Breusov
Serge Breusov

Reputation: 1396

  1. It really hard to understand desirable order in this method. But I will try. You use

    Queue.insert(pr, value);

so I assume that pr should be before value in case value>=*pr. That means descending order, from max to min.

  1. You want descending order. Then you need position when previous was bigger or equals and current element is less then value. So skip all until this position found and then insert.

    void PriorityQueue::Push(double value) {
   std::vector<double>::iterator pr;
   if (Queue.empty()) {
       Queue.push_back(value);
       return;
   }
   for (pr = Queue.begin(); pr != Queue.end(); pr++) {
        if (value < *pr)
            continue;
        Queue.insert(pr,value);
        break;
    }
}

And for ascending order - skip all until first that bigger and then insert:

    void PriorityQueue::Push(double value) {
       std::vector<double>::iterator pr;
       if (Queue.empty()) {
           Queue.push_back(value);
           return;
       }
       for (pr = Queue.begin(); pr != Queue.end(); pr++) {
            if (value >= *pr)
                continue;
            Queue.insert(pr,value);
            break;
        }
    }

  1. You don't need to check "if (value<0)" - I think your logical mistake was made at this step. Also you don't need to check

    if (!Queue.empty())

    in else-statement after

    if (Queue.empty())

    this is too much checking and can cause many mistakes...

Upvotes: 1

Related Questions