473,695 Members | 2,000 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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<typena me BidirectionalIt erator>
void quicksort(Bidir ectionalIterato r& begin, BidirectionalIt erator& end){
....
}
//partition function
template<typena me BidirectionalIt erator>
BidirectionalIt erator partition(Bidir ectionalIterato r& begin,
BidirectionalIt erator& end){
....
}
Jul 22 '05 #1
3 3573
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
RandomAccessInt erators, 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
RandomAccessInt erators, and one which takes those iterators and a
BinaryPredicate .....


My algorithm works for vectors and lists, by using BidirectionalIt erators.
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
RandomAccessInt erators, and one which takes those iterators and a
BinaryPredicate .....


My algorithm works for vectors and lists, by using
BidirectionalIt erators. 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
5446
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 procedure. I got javascript quicksort running, it's quick but it gets stack overflow after about 5000 elements. Am I passing the array as a parameter alright? I think javascript default is to pass pointers, that can be global.
1
1727
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, I think the only way one can pass the information is by using global or static variables.
2
4253
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' > function in the standard C library? I'm using gcc on mingw and assumed it was so minimal it wouldn't include it. Should've checked because it does of course. > As to your question, just invert all comparisons of the elements to be
0
1216
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 = myVector; int left = first; int right = last; swap(myVector, myVector);
6
944
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
640
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
6031
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
4376
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
3381
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 don't know how to fix it, doesn't even make sense why it would do it. Please help me out. Thanks in advance! Here is the error it gives me: TypeError: 'int' object is not iterable Here is my code: import random
0
8635
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9116
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
8990
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
8829
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7664
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6493
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
4342
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4580
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3007
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

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.