Merge Sort pissing me off

Merge Sort pissing me off

Post by Casval on Fri Sep 04, 2009 1:23 am
([msg=29061]see Merge Sort pissing me off[/msg])

I'm trying to get Merge Sort working for an array of Orders, here's the header file for the Order class:

Code: Select all
class Order
{
public:
   Order(int ID);
   Order();
   int GetID();
   string GetName();
   void SetName(string name);
   void SetID(int id);
   int GetBurgerCount();
   int GetFryCount();
   int GetDrinkCount();
   void ToString();
   ~Order();
private:
   string CreateRandomName();
   int custID;
   string custName;
   int burgerCount;
   int fryCount;
   int drinkCount;
};


The burgerCount, fryCount, and drinkCount don't mean anything at this point.
I'm trying to use Merge Sort to sort them by ID but I can't get the damn thing to work.
Any push in the right direction will be appreciated. Code follows...

Code: Select all
Order* merge(Order *left, int leftBounds, Order *right, int rightBounds)
{
   Order *result = new Order[leftBounds + rightBounds];
   int resultCounter = 0;
   int leftCounter = 0;
   int rightCounter = 0;
    while (leftCounter < leftBounds && rightCounter < rightBounds)
   {
        if (left[leftCounter].GetID() <= right[rightCounter].GetID())
      {
         result[resultCounter] = left[leftCounter];
            leftCounter++;
         resultCounter++;
      }
        else
      {
         result[resultCounter] = right[rightCounter];
         rightCounter++;
         resultCounter++;
      }
   }
    if (leftCounter < leftBounds)
        result[resultCounter] = left[leftCounter];
    else 
        result[resultCounter] = right[rightCounter];
    return result;

}

Order* MergeIDSort (Order *list, int leftBound, int rightBound)
{
   Order *left, *right, *result;
   int middle = 0;
   if (rightBound > 1)
   {
      middle = rightBound / 2 - 1;
      left = new Order[middle];
      right = new Order[middle];
      for (int i = 0; i < middle; i++)
         left[i] = list[i];
      int i = 0;
      for (int j = middle + 1; j < rightBound - 1; j++, i++)
         right[i] = list[j];
      left = MergeIDSort(list, 0, middle - 1);
      right = MergeIDSort(list, 0, rightBound - middle + 1);
      result = merge(left, leftBound, right, rightBound);
   }
   return result;
}
Casval
New User
New User
 
Posts: 24
Joined: Mon Apr 14, 2008 7:05 am
Blog: View Blog (0)


Re: Merge Sort pissing me off

Post by tgoe on Sat Sep 05, 2009 1:07 pm
([msg=29127]see Re: Merge Sort pissing me off[/msg])

You aren't calculating sizes and boundaries correctly for starters.
User avatar
tgoe
Contributor
Contributor
 
Posts: 718
Joined: Sun Sep 28, 2008 2:33 pm
Location: q3dm7
Blog: View Blog (0)


Re: Merge Sort pissing me off

Post by apples on Sat Feb 13, 2010 12:21 am
([msg=34969]see Re: Merge Sort pissing me off[/msg])

why don't you make this a templated function?
User avatar
apples
New User
New User
 
Posts: 37
Joined: Sat Apr 12, 2008 8:30 pm
Blog: View Blog (0)



Return to C and C++

Who is online

Users browsing this forum: No registered users and 0 guests