473,320 Members | 1,856 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Quicksort - compare function object

I want to make a quicksort algorithm that can take both a vector and a list.
This is the code I've got. But I also want to give an argument that will be
used for comparing the elements. I am used to programming in Lisp/Scheme,
where I would just pass a lambda. Is a function object something like that
in C++? And in that case, how would I pass the function/operator < (lesser
then).

//quicksort
template<typename BidirectionalIterator>
void quicksort(BidirectionalIterator& begin, BidirectionalIterator& end){
....
}
//partition function
template<typename BidirectionalIterator>
BidirectionalIterator partition(BidirectionalIterator& begin,
BidirectionalIterator& end){
....
}
Jul 22 '05 #1
3 3553
Lieven <li*************@hotmail.com> wrote in
news:41***********************@news.skynet.be:
I want to make a quicksort algorithm that can take both a vector and a
list. This is the code I've got. But I also want to give an argument
that will be used for comparing the elements. I am used to programming
in Lisp/Scheme, where I would just pass a lambda. Is a function object
something like that in C++? And in that case, how would I pass the
function/operator < (lesser then).


Umm.. any particular reason why you want to make your own quicksort vs.
using std::sort ?

And note that std::sort has two signatures... one which takes two
RandomAccessInterators, and one which takes those iterators and a
BinaryPredicate.....
Jul 22 '05 #2
Andre Kostur wrote:
Â*
Umm.. any particular reason why you want to make your own quicksort vs.
using std::sort ?

Yes, an excercise for school where we have to parallelize an algorithm. One
of the requirements if you have chosen a sort is that it is generic over
STL.
And note that std::sort has two signatures... one which takes two
RandomAccessInterators, and one which takes those iterators and a
BinaryPredicate.....


My algorithm works for vectors and lists, by using BidirectionalIterators.
But I wanted to know what is the best way to pass this predicate.
Jul 22 '05 #3
Lieven wrote in news:41***********************@news.skynet.be in
comp.lang.c++:
Andre Kostur wrote:
Â*
Umm.. any particular reason why you want to make your own quicksort
vs. using std::sort ?


Yes, an excercise for school where we have to parallelize an
algorithm. One of the requirements if you have chosen a sort is that
it is generic over STL.
And note that std::sort has two signatures... one which takes two
RandomAccessInterators, and one which takes those iterators and a
BinaryPredicate.....


My algorithm works for vectors and lists, by using
BidirectionalIterators. But I wanted to know what is the best way to
pass this predicate.


By (generic) value:

template< typename Bi, typename Comp >
void quicksort( Bi begin, Bi end, Comp comp )
{
// symantics: (bool)comp( *iter1, *iter2 ); with: Bi iter1, iter2;
}

Note that the iterators are also passed by value.

Example "Comp" aruguments for int:

std::less< int >(); // #include <functional>

bool f( int a, int b ) { return a < b; }

struct comp
{
typedef bool return_type;
bool operator( int a, int b ) const
{
return a < b;
}
};
int main()
{
std::vector< int > vi;
quicksort( vi.begin(), vi.end(), std::less< int >() );
quicksort( vi.begin(), vi.end(), f );
quicksort( vi.begin(), vi.end(), comp() );
}

Rob.
--
http://www.victim-prime.dsl.pipex.com/
Jul 22 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

36
by: HERC777 | last post by:
just paste the below into notepad, call it iqsort.html double click it and your IE browser will run it. (neat! a universal programming language we can all run!) it falls out from the sort...
1
by: Debashish Chakravarty | last post by:
Would it have been a good idea if the comparison function in quicksort took three const void * parameters in, the third one for extra information that might be required to compare the two objects,...
2
by: flipflop | last post by:
Martin Dickopp <expires-2004-06-30@zero-based.org> wrote in message news:<cunaczsrj0s.fsf@zero-based.org>... > > is there > any particular reason why you cannot or don't want to use the `qsort' >...
0
by: StephDawg40 | last post by:
I am attempting to write a Quicksort algorithm and my partition function is not behaving correctly. here is the code int CDataAnalyzerDlg::partition1(int first, int last) { int pivot =...
6
by: Baltazar007 | last post by:
Does anyone know how to make quicksort for single linked list without using array? I know that mergesort is maybe better but I need quicksort!! thnx
8
by: aparnakakkar2003 | last post by:
hello can any one tell me how i can create program to sort string list(standard template library) using quicksort.
8
by: aparnakakkar2003 | last post by:
hello can any one tell me how i can create program to sort string list(standard template library) using quicksort.
12
by: aparnakakkar2003 | last post by:
can any one tell me if I give the followiing string in input: ABC abc BBC then how I can get ABC abc BBC
3
by: jollyfolly | last post by:
Could you please help me find the error. I myself have (i might be wrong) boiled it down to the for loop because it somehow magically converts a list into an int and tries to iterate over that. But I...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.