# Algorithm to sort items in a vector container

• (3 Pages)
• 1
• 2
• 3

## 44 Replies - 2897 Views - Last Post: 07 May 2010 - 06:53 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=171828&amp;s=6546bb7128dde16a12ebdd4bcdf12620&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 wmugume2000

Reputation: 0
• 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 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 &, 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()) {
} 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;

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

• Engineer

Reputation: 1118
• Posts: 4,641
• 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

### #3 wmugume2000

Reputation: 0
• 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

### #4 r.stiltskin

• D.I.C Lover

Reputation: 1833
• 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

### #5 n8wxs

• --... ...-- -.. . -. ---.. .-- -..- ...

Reputation: 972
• 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
Press any key to continue . . .

```

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

### #6 wmugume2000

Reputation: 0
• 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 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 &, 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()) {
} 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;

show("Bids before sort:", bidlist);
sort(bidlist);
show("Bids after sort:", bidlist);

searchTest(bidlist, 3);
searchTest(bidlist, 33);
system("pause");
return 0;
}

```

### #7 n8wxs

• --... ...-- -.. . -. ---.. .-- -..- ...

Reputation: 972
• 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.

### #8 wmugume2000

Reputation: 0
• 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);
}

```

### #9 snoopy11

• Engineering ● Software

Reputation: 927
• Posts: 2,787
• 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.

### #10 wmugume2000

Reputation: 0
• 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()) {
} 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)); }
}

```

### #11 snoopy11

• Engineering ● Software

Reputation: 927
• Posts: 2,787
• 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 ?

### #12 wmugume2000

Reputation: 0
• 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)); }
}

```

### #13 r.stiltskin

• D.I.C Lover

Reputation: 1833
• 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?

### #14 wmugume2000

Reputation: 0
• 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!

### #15 r.stiltskin

• D.I.C Lover

Reputation: 1833
• 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).

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.