Algorithm to sort items in a vector container

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

44 Replies - 2757 Views - Last Post: 07 May 2010 - 06:53 PM Rate Topic: -----

#1 wmugume2000  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 130
  • Joined: 18-March 10

Algorithm to sort items in a vector container

Posted 03 May 2010 - 03:30 PM

I am trying to sort the contents of my container.An example below can show what am targeting

1.17, 5, B, 5, 105)
2(2, 11, B, 1, 89)
3(45, 1, A, 15, 94)
4(24, 6, B, 25, 110)

From above 3 matches 1 and 4.reasons:
Ones has an A and the other has a B, Price in A not higher than price in B
(the last field in each is price)

#include <iostream> 
#include <vector> 
#include <string> 
#include <algorithm> 
#include <cstdlib>  
 
using namespace std; 
 
const int NUMSELLER = 1; 
const int NUMBUYER = 1; 
const int NUMBIDS = 20; 
const int MINQUANTITY = 1; 
const int MAXQUANTITY = 30; 
const int MINPRICE =50; 
const int MAXPRICE = 100; 
 
// Bid, simple, its just a container for values 
struct Bid {  
        int bidId, trdId, qty, price;   
        char type; 
         
        // defining Operators to be  used for sorting to find  particular bids. 
        bool operator<(const Bid &other) const { return price < other.price; }  
        bool operator==(int bidId) const { return this->bidId == bidId; }  
};  
 
// An alias to the list to make type consistent 
typedef vector<Bid> BidList; 
 
// this class is for generates bids! 
class Simulator {  
private:  
        int nextBidId; 
 
public:  
        Simulator(); 
        Bid getNextBid(); 
        // the implication is in some place you want to choose the type 
        // I'm unclear on this, but you ca do it. 
        Bid getNextBid(char type); 
        // generate a number of bids 
        void loadRange(BidList &, int size); 
        void loadRange(BidList &, char type, int size); 
};  
 
Simulator::Simulator() : nextBidId(1) {} 
 
#define RAND_RANGE(min, max) ((rand() % (max-min+1)) + min) 
         
Bid Simulator::getNextBid() { 
        //int i=0;
        char type = RAND_RANGE('A','B');  
        //if (i<10){type='A';}else {type='B';}
        return getNextBid(type);

} 
 
Bid Simulator::getNextBid(char type) { 
        int trdId = RAND_RANGE(1,9);  
        int qty = RAND_RANGE(MINQUANTITY, MAXQUANTITY);  
        int price = RAND_RANGE(MINPRICE, MAXPRICE); 
        Bid bid = {nextBidId++, trdId, qty, price, type}; 
        return bid; 
} 
 
 
void Simulator::loadRange(BidList &list, int size) { 
        for (int i=0; i<size; i++) {list.push_back(getNextBid()); } 
} 
 
void Simulator::loadRange(BidList &list, char type, int size) { 
        for (int i=0; i<size; i++) { list.push_back(getNextBid(type)); } 
} 
 
// all the display commands 
void show(const Bid &bid) {  
        //Alogorithm to ensure that there are only 10 B, bids and 10 A bids
        cout  << bid.bidId << '\t' << bid.trdId << '\t' << bid.type << '\t' << bid.qty << '\t' << bid.price;  
}  
 
void show(const BidList &list) {  
        cout <<"\t\tBidID | TradID | Type  | Qty  |  Price  \n\n";   
        for(BidList::const_iterator itr=list.begin(); itr != list.end(); ++itr) { 
                cout <<"\t\t ( ";  
                show(*itr); 
                cout <<" )"; 
                cout << endl;  
        }  
        cout << endl;  
}  
 
void show(const char *msg, const BidList &list) {  
        cout << msg << endl; 
        show(list); 
} 
 
// search now checks for failure 
void searchTest(BidList &list, int bidId) {  
        cout << "Searching for Bid " << bidId << endl; 
        BidList::const_iterator itr = find(list.begin(), list.end(), bidId);  
        if (itr==list.end()) { 
                cout << "Bid not found.";  
        } else { 
                cout << "Bid has been found. Its : ";  
                show(*itr); 
        } 
        cout << endl;  
}  
 
void sort(BidList &bidlist) { sort(bidlist.begin(), bidlist.end()); } 
 
int main() {  
        Simulator simulator; 
        BidList bidlist;  
 
        simulator.loadRange(bidlist, NUMBIDS); 
        show("Bids before sort:", bidlist);  
        sort(bidlist);  
        show("Bids after sort:", bidlist);  
         
        searchTest(bidlist, 3);  
        searchTest(bidlist, 33);  
         system("pause");
        return 0;  
}



Is This A Good Question/Topic? 0
  • +

Replies To: Algorithm to sort items in a vector container

#2 jjl  Icon User is offline

  • Engineer
  • member icon

Reputation: 1112
  • View blog
  • Posts: 4,619
  • Joined: 09-June 09

Re: Algorithm to sort items in a vector container

Posted 03 May 2010 - 04:04 PM

there is a sort function within
#include <algorithm>


which will sort a vector, you can pass in your own comparison function for sorting

This post has been edited by ImaSexy: 03 May 2010 - 04:04 PM

Was This Post Helpful? 0
  • +
  • -

#3 wmugume2000  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 130
  • Joined: 18-March 10

Re: Algorithm to sort items in a vector container

Posted 03 May 2010 - 04:17 PM

I have the sort there, but I dont know how to use it to make the comparison based on two of the elements character and price
Was This Post Helpful? 0
  • +
  • -

#4 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Algorithm to sort items in a vector container

Posted 03 May 2010 - 07:59 PM

To use the STL sort functions to sort your class or struct objects you have to provide a comparator function. In this case, you have to sort twice -- first on bid type, then on bid price, so you need two comparators. Also to be sure that the second sort doesn't mess up what the first sort accomplished, you should use stable_sort.

// comparator function for type: returns true when x belongs before y
bool compare_bid_type( const Bid& x, const Bid& y )
{
	return x.type <= y.type;
}

// comparator function for price: returns true when x belongs before y
bool compare_bid_price( const Bid& x, const Bid& y )
{
	return x.price <= y.price;
}

void sort( BidList &bidlist )
{
    stable_sort( bidlist.begin(), bidlist.end(), compare_bid_type );
    stable_sort( bidlist.begin(), bidlist.end(), compare_bid_price );
}



note: put the comparator functions anyplace after the definition of Bid, and before the definition of sort.

This post has been edited by r.stiltskin: 03 May 2010 - 08:04 PM

Was This Post Helpful? 0
  • +
  • -

#5 n8wxs  Icon User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 972
  • View blog
  • Posts: 3,878
  • Joined: 07-January 08

Re: Algorithm to sort items in a vector container

Posted 03 May 2010 - 08:41 PM

How 'bout:

...
bool compareBidList(Bid one, Bid two) {

	if (one.type == 'A' && two.type == 'B')
		return (one.price < two.price);

	return false;
}

void sort(BidList &bidlist) { sort(bidlist.begin(), bidlist.end(), compareBidList); } 
...



output:

Bids before sort:
                BidID | TradID | Type  | Qty  |  Price

                 ( 1    9       B       5       81 )
                 ( 2    2       B       19      83 )
                 ( 3    3       A       6       94 )
                 ( 4    7       B       2       82 )
                 ( 5    9       B       28      80 )
                 ( 6    7       B       3       50 )
                 ( 7    8       A       22      100 )
                 ( 8    6       A       18      50 )
                 ( 9    1       B       10      72 )
                 ( 10   2       B       26      50 )
                 ( 11   7       B       3       89 )
                 ( 12   3       B       22      60 )
                 ( 13   2       B       18      52 )
                 ( 14   7       A       28      57 )
                 ( 15   4       B       20      63 )
                 ( 16   3       A       21      56 )
                 ( 17   2       A       11      67 )
                 ( 18   5       A       27      89 )
                 ( 19   7       A       11      100 )
                 ( 20   7       A       4       79 )

Bids after sort:
                BidID | TradID | Type  | Qty  |  Price

                 ( 8    6       A       18      50 )
                 ( 1    9       B       5       81 )

                 ( 2    2       B       19      83 )
                 ( 3    3       A       6       94 )

                 ( 4    7       B       2       82 )
                 ( 5    9       B       28      80 )

                 ( 6    7       B       3       50 )
                 ( 7    8       A       22      100 )

                 ( 9    1       B       10      72 )
                 ( 10   2       B       26      50 )

                 ( 11   7       B       3       89 )
                 ( 12   3       B       22      60 )

                 ( 13   2       B       18      52 )
                 ( 14   7       A       28      57 )

                 ( 16   3       A       21      56 )
                 ( 15   4       B       20      63 )

                 ( 17   2       A       11      67 )
                 ( 18   5       A       27      89 )

                 ( 19   7       A       11      100 )
                 ( 20   7       A       4       79 )

Searching for Bid 3
Bid has been found. Its : 3     3       A       6       94
Searching for Bid 33
Bid not found.
Press any key to continue . . .


This post has been edited by n8wxs: 03 May 2010 - 08:43 PM

Was This Post Helpful? 0
  • +
  • -

#6 wmugume2000  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 130
  • Joined: 18-March 10

Re: Algorithm to sort items in a vector container

Posted 03 May 2010 - 11:26 PM

Thanks so much! I have been looking through the paired bids, I just noticed that it didnt take into consideration that 1 bid can match more than one.probably such a situation never arised.I have tried to increase the bids to see the effect in action.THis is the lates code.

How can I control the output of the paired bids, I would like to show them as below, and then show the unpaired separate.

( 6 7 B 3 50 ) ( 1 9 B 5 81 )

Unpaired Bids
........

#include <iostream> 
#include <vector> 
#include <string> 
#include <algorithm> 
#include <cstdlib>
#include <iomanip>   
 
using namespace std; 
 
const int NUMSELLER = 1; 
const int NUMBUYER = 1; 
const int NUMBIDS = 20; 
const int MINQUANTITY = 1; 
const int MAXQUANTITY = 30; 
const int MINPRICE =100; 
const int MAXPRICE = 150; 
 
// Bid, simple, stupid, just a container for values 
struct Bid {  
        int bidId, trdId, qty, price;   
        char type; 
         
        // for sort and find.  could put this elsewhere, but would take more work. 
        bool operator<(const Bid &other) const { return price < other.price; }  
        bool operator==(int bidId) const { return this->bidId == bidId; }  
};  
 
// alias to the list, make type consistent 
typedef vector<Bid> BidList; 
 
// this class generates bids! 
class Simulator {  
private:  
        int nextBidId; 
 
public:  
        Simulator(); 
        Bid getNextBid(); 
        // the implication is in some place you want to choose the type 
        // I'm unclear on this, but you ca do it. 
        Bid getNextBid(char type); 
        // generate a number of bids 
        void loadRange(BidList &, int size); 
        void loadRange(BidList &, char type, int size); 
};  
 
Simulator::Simulator() : nextBidId(1) {} 
 
#define RAND_RANGE(min, max) ((rand() % (max-min+1)) + min) 
         
Bid Simulator::getNextBid() { 
        char type = RAND_RANGE('A','B');  
        return getNextBid(type); 
} 
 
Bid Simulator::getNextBid(char type) { 
        int trdId = RAND_RANGE(1,9);  
        int qty = RAND_RANGE(MINQUANTITY, MAXQUANTITY);  
        int price = RAND_RANGE(MINPRICE, MAXPRICE); 
        Bid bid = {nextBidId++, trdId, qty, price, type}; 
        return bid; 
} 
 
 
void Simulator::loadRange(BidList &list, int size) { 
        for (int i=0; i<size; i++) { list.push_back(getNextBid()); } 
} 
 
void Simulator::loadRange(BidList &list, char type, int size) { 
        for (int i=0; i<size; i++) { list.push_back(getNextBid(type)); } 
} 
 
// all the happy display commands 
void show(const Bid &bid) {  
     cout << "\tBid\t(" <<  setw(3) << bid.bidId << "\t " << setw(3) << bid.trdId  << "\t " 
     << setw(3) <<  bid.type <<"\t " << setw(3) << bid.qty <<"\t "  << setw(3) << bid.price <<")\t\n "  ;    
}  
 
void show(const BidList &list) {  
        cout << "\t\tBidID | TradID | Type  | Qty  |  Price  \n\n";   
        for(BidList::const_iterator itr=list.begin(); itr != list.end(); ++itr) {  
                //cout <<"\t\t";  
                show(*itr); 
                cout << endl;  
        }  
        cout << endl;  
} 
 
void show(const char *msg, const BidList &list) {  
        cout << msg << endl; 
        show(list); 
} 
 
// search now checks for failure 
void searchTest(BidList &list, int bidId) {  
        cout << "Searching for Bid " << bidId << endl; 
        BidList::const_iterator itr = find(list.begin(), list.end(), bidId);  
        if (itr==list.end()) { 
                cout << "Bid not found.";  
        } else { 
                cout << "Bid has been found. Its : ";  
                show(*itr); 
        } 
        cout << endl;  
}  
 
//void sort(BidList &bidlist) { sort(bidlist.begin(), bidlist.end()); } 
bool compareBidList(Bid one, Bid two) { 
 
        if (one.type == 'A' && two.type == 'B') 
                return (one.price < two.price); 
 
        return false; 
} 
 
void sort(BidList &bidlist) { sort(bidlist.begin(), bidlist.end(), compareBidList); }  

 
int main() {  
        Simulator simulator; 
        BidList bidlist;  
 
        simulator.loadRange(bidlist, NUMBIDS); 
        show("Bids before sort:", bidlist);  
        sort(bidlist);  
        show("Bids after sort:", bidlist);  
         
        searchTest(bidlist, 3);  
        searchTest(bidlist, 33);  
         system("pause");
        return 0;  
}




Was This Post Helpful? 0
  • +
  • -

#7 n8wxs  Icon User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 972
  • View blog
  • Posts: 3,878
  • Joined: 07-January 08

Re: Algorithm to sort items in a vector container

Posted 03 May 2010 - 11:43 PM

You could use a second vector to hold the paired bids.
Was This Post Helpful? 0
  • +
  • -

#8 wmugume2000  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 130
  • Joined: 18-March 10

Re: Algorithm to sort items in a vector container

Posted 04 May 2010 - 01:33 AM

I have a big problem with vectors.Well have created the second vector meant to hold the paired bids, but copying the bids into it is still a problem.


typedef vector<Bid> BidList,Sorted; 

void sort(BidList &bidlist) { sort(bidlist.begin(), bidlist.end(), compareBidList); }  
// Definitions for the second container

void Simulator::showSorted(Sorted &list, int size) { 
        for (int i=0; i<size; i++) { list.push_back(getNextBid()); } 
} 
 
void Simulator::showSorted(Sorted &list, char type, int size) { 
        for (int i=0; i<size; i++) { list.push_back(getNextBid(type)); } 
} 

void display(const Bid &bid)
{  
     cout << "\tBid\t(" <<  setw(3) << bid.bidId << "\t " << setw(3) << bid.trdId  << "\t " 
     << setw(3) <<  bid.type <<"\t " << setw(3) << bid.qty <<"\t "  << setw(3) << bid.price <<")\t\n "  ;    
}  

void display(const Sorted &list) {  
        for(Sorted::const_iterator itr=list.begin(); itr != list.end(); ++itr) {  
                //cout <<"\t\t";  
                display(*itr); 
                cout << endl;  
        }  
        cout << endl;  
} 
void display(const char *msg, const Sorted &list) {  
        cout << msg << endl; 
        display(list); 
} 



Was This Post Helpful? 0
  • +
  • -

#9 snoopy11  Icon User is online

  • Engineering ● Software
  • member icon

Reputation: 841
  • View blog
  • Posts: 2,472
  • Joined: 20-March 10

Re: Algorithm to sort items in a vector container

Posted 04 May 2010 - 01:54 AM

you have two functions with the same name

void Simulator::showSorted(Sorted &list, int size) { 
        for (int i=0; i<size; i++) { list.push_back(getNextBid()); } 
} 
 
void Simulator::showSorted(Sorted &list, char type, int size) { 
        for (int i=0; i<size; i++) 
{
 list.push_back(getNextBid(type)); 
} 
} 




you need to rename one of them.
Was This Post Helpful? 0
  • +
  • -

#10 wmugume2000  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 130
  • Joined: 18-March 10

Re: Algorithm to sort items in a vector container

Posted 04 May 2010 - 02:06 AM

They are same but with different parameters.just like in this code, which I was using for displaying the bid.You will realise that one has a char type whereas another does not!


void show(const Bid &bid) {  
     cout << "\tBid\t(" <<  setw(3) << bid.bidId << "\t " << setw(3) << bid.trdId  << "\t " 
     << setw(3) <<  bid.type <<"\t " << setw(3) << bid.qty <<"\t "  << setw(3) << bid.price <<")\t\n "  ;    
}  
  
void show(const BidList &list) {  
        cout << "\t\tBidID | TradID | Type  | Qty  |  Price  \n\n";   
        for(BidList::const_iterator itr=list.begin(); itr != list.end(); ++itr) {  
                //cout <<"\t\t";  
                show(*itr); 
                cout << endl;  
        }  
        cout << endl;  
} 
 
void show(const char *msg, const BidList &list) {  
        cout << msg << endl; 
        show(list); 
} 
 
// search now checks for failure 
void searchTest(BidList &list, int bidId) {  
        cout << "Searching for Bid " << bidId << endl; 
        BidList::const_iterator itr = find(list.begin(), list.end(), bidId);  
        if (itr==list.end()) { 
                cout << "Bid not found.";  
        } else { 
                cout << "Bid has been found. Its : ";  
                show(*itr); 
        } 
        cout << endl;  
}  
 
//void sort(BidList &bidlist) { sort(bidlist.begin(), bidlist.end()); } 
bool compareBidList(Bid one, Bid two) { 
 
        if (one.type == 'A' && two.type == 'B') 
                return (one.price < two.price); 
 
        return false; 
} 
 
void sort(BidList &bidlist) { sort(bidlist.begin(), bidlist.end(), compareBidList); }  
// Definitions for the second container

void Simulator::showSorted(Sorted &list, int size) { 
        for (int i=0; i<size; i++) { list.push_back(getNextBid()); } 
} 
 
void Simulator::showSorted(Sorted &list, char type, int size) { 
        for (int i=0; i<size; i++) { list.push_back(getNextBid(type)); } 
} 


Was This Post Helpful? 0
  • +
  • -

#11 snoopy11  Icon User is online

  • Engineering ● Software
  • member icon

Reputation: 841
  • View blog
  • Posts: 2,472
  • Joined: 20-March 10

Re: Algorithm to sort items in a vector container

Posted 04 May 2010 - 02:09 AM

yeah its a bit confusing

why do you do that dude why just not name it something else ?
Was This Post Helpful? 0
  • +
  • -

#12 wmugume2000  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 130
  • Joined: 18-March 10

Re: Algorithm to sort items in a vector container

Posted 04 May 2010 - 02:27 AM

I have renamed it but still am not geting good results.Trying to figure out how to copy all sorted bids from the first vector and then insert them in the second one, before I call display.
void Simulator::showSorted2(Sorted &list, char type, int size) { 
        for (int i=0; i<size; i++) { list.push_back(getNextBid(type)); } 
} 


Was This Post Helpful? 0
  • +
  • -

#13 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Algorithm to sort items in a vector container

Posted 04 May 2010 - 07:31 AM

What does "not getting good results" mean?

Sorting the bids was just a mechanical task. And once you have matched the buyers and sellers, displaying them should also be a straightforward, mechanical task.

Presumably, the underlying goal of your auction is to maximize the number or value of goods sold. The crucial step is to decide on an algorithm for matching buyers with sellers -- who gets to trade, and how much (and at what price)? Are the "winning" buyers the ones that offered the highest price? That's the case in the English Auction (the one we're most familiar with), but it's not true in all auctions. So that's the first thing you have to decide. Next you have to decide how you will deal with the fact that your bids vary as to quantity. Once you have decided those two factors the rest should be relatively easy. So, rather than trying immediately to produce output, can you first articulate (in words) exactly what your matching process/algorithm is? What are the "rules" of your auction?
Was This Post Helpful? 0
  • +
  • -

#14 wmugume2000  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 130
  • Joined: 18-March 10

Re: Algorithm to sort items in a vector container

Posted 04 May 2010 - 10:15 AM

These are the rules of the auction.An example below can show what am targeting.I am targeting marting out the bids, and its from the matches that I will calculate the profit rather than from a particular high price bid.
One has to have an A and the other has a B, Price in A not higher than price in B
(the last field in each is price).Below, bid 3 matches bids 1 and 4.So in the pool of bids, most bids will get a match.I move the matched to another container and I will then dump those un-matched to another container as residual bids.

1.17, 5, B, 5, 105)
2(2, 11, B, 1, 89)
3(45, 1, A, 15, 94)
4(24, 6, B, 25, 110)

I will so greatful for your assitance here....all my tries are just hiting a rock!
Was This Post Helpful? 0
  • +
  • -

#15 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • Posts: 4,927
  • Joined: 27-December 05

Re: Algorithm to sort items in a vector container

Posted 04 May 2010 - 12:06 PM

To avoid ambiguity, I'm going to call your "Bids" shouts. I'll use "bid" to refer to your "type B" shouts (that's the price a buyer is willing to pay) and I'll use "ask" to refer to your "type A" shouts (the price a seller is asking for the product).

You seem to be ignoring the quantity stated in each shout, which is a key aspect of the auction. In the example you just mentioned, yes, buyers 5 and 6 are both 'eligible' to participate in a trade with seller 1 based just on the shout prices. But seller 1 is only offering to sell 15 units, while buyer 6 wants to buy 25, and buyer 5 wants to buy 5. So you still have 2 decisions to make: which buyer gets to buy from seller 1 -- buyer 5 or buyer 6, or do they each get to buy part of the seller's 15 units? And what will be the actual sale price -- will it be the seller's "ask" price, or the buyer's "bid" price, or something in between. Any of those is reasonable, but before you can write the program, you have to decide on the rules.

In the above example, you had eligible buyers whose combined demand is greater than the amount offered by the seller. You can also have the opposite -- a seller offering a greater quantity than the quantity wanted by the eligible buyers. So you also need a rule to deal with that situation. Here is a sample output generated after sorting the shouts the way I showed you last night:

Bids after sort:
                BidID | TradID | Type  | Qty  |  Price

                 ( 19   1       A       15      50 )
                 ( 16   1       B       15      53 )
                 ( 7    9       A       3       54 )
                 ( 14   9       B       27      56 )
                 ( 8    2       B       30      65 )
                 ( 4    8       A       24      72 )
                 ( 15   6       A       17      72 )
                 ( 11   1       B       22      73 )
                 ( 13   4       B       24      78 )
                 ( 3    2       B       3       81 )
                 ( 10   8       B       2       81 )
                 ( 5    1       A       23      81 )
                 ( 9    4       A       30      83 )
                 ( 1    8       B       28      84 )
                 ( 20   6       A       4       88 )
                 ( 6    9       B       28      89 )
                 ( 17   9       A       17      89 )
                 ( 12   5       A       9       97 )
                 ( 2    8       B       17      98 )
                 ( 18   3       B       25      98 )



I suggest you take that and work out on paper how you want to divvy up the goods, and maybe that will help you organize your thoughts so you'll be able to program it.
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3