Quicksort for list of string

A

aparnakakkar2003

can any one tell me if I give the followiing string in input:
ABC
abc
BBC

then how I can get
ABC
abc
BBC


or

abc
ABC
BBC
as my output usiing quicksort.
 
?

=?iso-8859-1?q?Erik_Wikstr=F6m?=

can any one tell me if I give the followiing string in input:
ABC
abc
BBC

then how I can get
ABC
abc
BBC

or

abc
ABC
BBC
as my output usiing quicksort.
Click to expand...

Don't know about quicksort but if it's sorting you want then given a
number of strings read from some input store them in a std::vector and
use std::sort() on them. Don't know the exact ordering of strings but
I'd guess that capital letters are sorted before lowercase letters so
the most likely result would be:

ABC
abc
BBC
 
V

Victor Bazarov

Erik said:
Don't know about quicksort but if it's sorting you want then given a
number of strings read from some input store them in a std::vector and
use std::sort() on them. Don't know the exact ordering of strings but
I'd guess that capital letters are sorted before lowercase letters so
the most likely result would be:

ABC
abc
BBC
Click to expand...

*All* capital letters come before *any* lowercase ones. So, the result
*should* be

ABC
BBC
abc

V
 
A

aparnakakkar2003

*All* capital letters come before *any* lowercase ones. So, the result
*should* be

ABC
BBC
abc

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask- Hide quoted text -

- Show quoted text -
Click to expand...

but I want in that way only can you tell me how ,that sort function
will not give this result.
 
V

Victor Bazarov

but I want in that way only can you tell me how ,that sort function
will not give this result.
Click to expand...

Well, I wasn't replying to you, I was replyting to Erik.

And, sorry, I don't understand the last sentence you posted. Could
you perhaps rephrase it using a few shorter sentences?

Neither C++ strings (objects of type 'std::string') nor C strings
(arrays of char) can be sorted using 'quicksort' (generally speaking).

To sort 'std::string' objects, use 'std::sort' (which most likely
implements Quick Sort algorithm), or the 'sort' member of the 'list'
container (if your strings are in a 'list' container).

In order to use 'qsort' function, you'd have to define your own
data structures, your own comparator, and then place your data in
an array, and then call 'qsort'. If that's your how you want to do
that, fine; it's not the best C++ way, however.

V
 
J

Jim Langston

can any one tell me if I give the followiing string in input:
ABC
abc
BBC

then how I can get
ABC
abc
BBC


or

abc
ABC
BBC
as my output usiing quicksort.
Click to expand...

Well, this doesn't use quicksort but std::sort which is O( N log N ).

Output is:

Before sort:
ABC
abc
BBC
ABCD
aB

After sort:
ABC
ABCD
BBC
aB
abc

After Case Insensitive sort:
aB
ABC
abc
ABCD
BBC

There may be a better/faster algorithm for the case insensitve comparing of
std::strings. I just did this one rather quickly.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

bool CILessthan( const std::string Elem1, const std::string Elem2 )
{
for ( std::size_t i = 0; i < Elem1.length(); ++i )
{
if ( std::tolower( Elem1 ) < std::tolower( Elem2 ) )
return true;
else if ( std::tolower( Elem1 ) > std::tolower( Elem2 ) )
return false;
}

// Equal up to this point, but one may be longer
if ( Elem1.length() < Elem2.length() )
return true;

return false;
}

void ShowData( const std::vector<std::string>& Data )
{
for ( std::vector<std::string>::const_iterator it = Data.begin(); it !=
Data.end(); ++it )
std::cout << (*it) << "\n";
}

int main()
{
std::vector<std::string> Data;
Data.push_back( "ABC" );
Data.push_back( "abc" );
Data.push_back( "BBC" );
Data.push_back( "ABCD" );
Data.push_back( "aB" );

std::cout << "Before sort:\n";
ShowData( Data );

std::sort( Data.begin(), Data.end() );
std::cout << "\nAfter sort:\n";
ShowData( Data );

std::sort( Data.begin(), Data.end(), CILessthan );
std::cout << "\nAfter Case Insensitive sort:\n";
ShowData( Data );

std::string wait;
std::getline( std::cin, wait );
}
 
A

aparnakakkar2003

can any one tell me if I give the followiing string in input:
ABC
abc
BBC
Click to expand...
then how I can get
ABC
abc
BBC

abc
ABC
BBC
as my output usiing quicksort.
Click to expand...

Well, this doesn't use quicksort but std::sort which is O( N log N ).

Output is:

Before sort:
ABC
abc
BBC
ABCD
aB

After sort:
ABC
ABCD
BBC
aB
abc

After Case Insensitive sort:
aB
ABC
abc
ABCD
BBC

There may be a better/faster algorithm for the case insensitve comparing of
std::strings. I just did this one rather quickly.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

bool CILessthan( const std::string Elem1, const std::string Elem2 )
{
for ( std::size_t i = 0; i < Elem1.length(); ++i )
{
if ( std::tolower( Elem1 ) < std::tolower( Elem2 ) )
return true;
else if ( std::tolower( Elem1 ) > std::tolower( Elem2 ) )
return false;
}

// Equal up to this point, but one may be longer
if ( Elem1.length() < Elem2.length() )
return true;

return false;

}

void ShowData( const std::vector<std::string>& Data )
{
for ( std::vector<std::string>::const_iterator it = Data.begin(); it !=
Data.end(); ++it )
std::cout << (*it) << "\n";

}

int main()
{
std::vector<std::string> Data;
Data.push_back( "ABC" );
Data.push_back( "abc" );
Data.push_back( "BBC" );
Data.push_back( "ABCD" );
Data.push_back( "aB" );

std::cout << "Before sort:\n";
ShowData( Data );

std::sort( Data.begin(), Data.end() );
std::cout << "\nAfter sort:\n";
ShowData( Data );

std::sort( Data.begin(), Data.end(), CILessthan );
std::cout << "\nAfter Case Insensitive sort:\n";
ShowData( Data );

std::string wait;
std::getline( std::cin, wait );



}- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -
Click to expand...


please tell me how is it possible with (std::list<std::string> data)
as an argument
 
J

Jim Langston

can any one tell me if I give the followiing string in input:
ABC
abc
BBC
Click to expand...
then how I can get
ABC
abc
BBC

abc
ABC
BBC
as my output usiing quicksort.
Click to expand...

Well, this doesn't use quicksort but std::sort which is O( N log N ).

Output is:

Before sort:
ABC
abc
BBC
ABCD
aB

After sort:
ABC
ABCD
BBC
aB
abc

After Case Insensitive sort:
aB
ABC
abc
ABCD
BBC

There may be a better/faster algorithm for the case insensitve comparing
of
std::strings. I just did this one rather quickly.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

bool CILessthan( const std::string Elem1, const std::string Elem2 )
{
for ( std::size_t i = 0; i < Elem1.length(); ++i )
{
if ( std::tolower( Elem1 ) < std::tolower( Elem2 ) )
return true;
else if ( std::tolower( Elem1 ) > std::tolower( Elem2 ) )
return false;
}

// Equal up to this point, but one may be longer
if ( Elem1.length() < Elem2.length() )
return true;

return false;

}

void ShowData( const std::vector<std::string>& Data )
{
for ( std::vector<std::string>::const_iterator it = Data.begin(); it
!=
Data.end(); ++it )
std::cout << (*it) << "\n";

}

int main()
{
std::vector<std::string> Data;
Data.push_back( "ABC" );
Data.push_back( "abc" );
Data.push_back( "BBC" );
Data.push_back( "ABCD" );
Data.push_back( "aB" );

std::cout << "Before sort:\n";
ShowData( Data );

std::sort( Data.begin(), Data.end() );
std::cout << "\nAfter sort:\n";
ShowData( Data );

std::sort( Data.begin(), Data.end(), CILessthan );
std::cout << "\nAfter Case Insensitive sort:\n";
ShowData( Data );

std::string wait;
std::getline( std::cin, wait );



}- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -
Click to expand...


please tell me how is it possible with (std::list<std::string> data)
as an argument
Click to expand...


Just replace
std::sort( Data.begin(), Data.end(); CILessthan );
with
Data.sort( CILessthan );

As long as it's a list and not a vector.
 
J

James Kanze

*All* capital letters come before *any* lowercase ones.
Click to expand...

That's actually platform dependant (and so off-topic here:).
On an IBM mainframe, capital letters come after lowercase (and
there are some punctuation signs which show up in the middle of
the alphabet). On my system (Solaris), some of the capitals
even have negative values---forcing them to an unsigned char
results in two blocks of capitals, and two of small letters,
interleaved (with some punctuation and some control characters
between them).

That's why when the order is significant to a human being,
you'll almost always use a locale specific collating function.
 
A

aparnakakkar2003

That's actually platform dependant (and so off-topic here:).
On an IBM mainframe, capital letters come after lowercase (and
there are some punctuation signs which show up in the middle of
the alphabet). On my system (Solaris), some of the capitals
even have negative values---forcing them to an unsigned char
results in two blocks of capitals, and two of small letters,
interleaved (with some punctuation and some control characters
between them).

That's why when the order is significant to a human being,
you'll almost always use a locale specific collating function.

--
James Kanze (GABI Software) email:[email protected]
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34- Hide quoted text -

- Show quoted text -
Click to expand...

can any one tell me i f the code below will work or not

void QuickSortList(VR_STRINGList::iterator
pLeft,VR_STRINGList::iterator pRight)
{
VR_STRINGList ::iterator pStart;
VR_STRINGList ::iterator pCurrent;
// VR_STRINGList ::iterator nCopyInteger; // If the left and
right pointers are the same, then return

VR_STRING nCopyInteger;

if (pLeft == pRight)
return;

pStart = pLeft;
pCurrent = pStart++; // Loop forever (well until we get to the
right)
while (1)
{
if(strcmpi(pStart->c_str(),pCurrent->c_str())<0)
{


nCopyInteger = *pCurrent;
*pCurrent = *pStart;
*pStart = nCopyInteger;
}
if (pCurrent == pRight)
break;
pCurrent = pCurrent++;
}

nCopyInteger = *pLeft;
*pLeft = *pCurrent;
*pCurrent= nCopyInteger;

VR_STRINGList ::iterator pOldCurrent;


*pOldCurrent = *pCurrent;
pCurrent = pCurrent--;

if (pCurrent != NULL)
{
if ((pLeft-- != pCurrent) && (pCurrent++ != pLeft))
QuickSortList(pLeft,pCurrent);
}

pCurrent = pOldCurrent;
pCurrent = pCurrent++;
if (pCurrent != NULL)
{
if ((pCurrent-- != pRight) && (pRight++ != pCurrent))
QuickSortList(pCurrent, pRight);
}
}
Tell me problem please I am not getting the output.
 
J

Jim Langston

can any one tell me if I give the followiing string in input:
ABC
abc
BBC
then how I can get
ABC
abc
BBC
or
abc
ABC
BBC
as my output usiing quicksort.
Well, this doesn't use quicksort but std::sort which is O( N log N ).
Output is:
Before sort:
ABC
abc
BBC
ABCD
aB
After sort:
ABC
ABCD
BBC
aB
abc
After Case Insensitive sort:
aB
ABC
abc
ABCD
BBC
There may be a better/faster algorithm for the case insensitve
comparing
of
std::strings. I just did this one rather quickly.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
bool CILessthan( const std::string Elem1, const std::string Elem2 )
{
for ( std::size_t i = 0; i < Elem1.length(); ++i )
{
if ( std::tolower( Elem1 ) < std::tolower( Elem2 ) )
return true;
else if ( std::tolower( Elem1 ) > std::tolower( Elem2 ) )
return false;
}
// Equal up to this point, but one may be longer
if ( Elem1.length() < Elem2.length() )
return true;
return false;
}
void ShowData( const std::vector<std::string>& Data )
{
for ( std::vector<std::string>::const_iterator it = Data.begin();
it
!=
Data.end(); ++it )
std::cout << (*it) << "\n";
}
int main()
{
std::vector<std::string> Data;
Data.push_back( "ABC" );
Data.push_back( "abc" );
Data.push_back( "BBC" );
Data.push_back( "ABCD" );
Data.push_back( "aB" );
std::cout << "Before sort:\n";
ShowData( Data );
std::sort( Data.begin(), Data.end() );
std::cout << "\nAfter sort:\n";
ShowData( Data );
std::sort( Data.begin(), Data.end(), CILessthan );
std::cout << "\nAfter Case Insensitive sort:\n";
ShowData( Data );
std::string wait;
std::getline( std::cin, wait );
}- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
Click to expand...
Click to expand...

please tell me how is it possible with (std::list<std::string> data)
as an argument
Click to expand...

Just replace
std::sort( Data.begin(), Data.end(); CILessthan );
with
Data.sort( CILessthan );

As long as it's a list and not a vector.- Hide quoted text -
Click to expand...


Its not working I want Data to be of type " std::list<std::string>
Data;"

--------

Please don't send questions to my e-mail, post them here.

In this program if you replace every occurance of "vector" with "list",
change
std::sort( Data.begin(), Data.end(); CILessthan );
with
Data.sort( CILessthan );

and compile it should run fine.
 
A

aparnakakkar2003

news:[email protected]...
Click to expand...
can any one tell me if I give the followiing string in input:
ABC
abc
BBC
then how I can get
ABC
abc
BBC
or
abc
ABC
BBC
as my output usiing quicksort.
Well, this doesn't use quicksort but std::sort which is O( N log N ).
Output is:
Before sort:
ABC
abc
BBC
ABCD
aB
After sort:
ABC
ABCD
BBC
aB
abc
After Case Insensitive sort:
aB
ABC
abc
ABCD
BBC
There may be a better/faster algorithm for the case insensitve
comparing
of
std::strings. I just did this one rather quickly.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
bool CILessthan( const std::string Elem1, const std::string Elem2 )
{
for ( std::size_t i = 0; i < Elem1.length(); ++i )
{
if ( std::tolower( Elem1 ) < std::tolower( Elem2 ) )
return true;
else if ( std::tolower( Elem1 ) > std::tolower( Elem2 ) )
return false;
}
// Equal up to this point, but one may be longer
if ( Elem1.length() < Elem2.length() )
return true;
return false;
}
void ShowData( const std::vector<std::string>& Data )
{
for ( std::vector<std::string>::const_iterator it = Data.begin();
it
!=
Data.end(); ++it )
std::cout << (*it) << "\n";
}
int main()
{
std::vector<std::string> Data;
Data.push_back( "ABC" );
Data.push_back( "abc" );
Data.push_back( "BBC" );
Data.push_back( "ABCD" );
Data.push_back( "aB" );
std::cout << "Before sort:\n";
ShowData( Data );
std::sort( Data.begin(), Data.end() );
std::cout << "\nAfter sort:\n";
ShowData( Data );
std::sort( Data.begin(), Data.end(), CILessthan );
std::cout << "\nAfter Case Insensitive sort:\n";
ShowData( Data );
std::string wait;
std::getline( std::cin, wait );
}- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
please tell me how is it possible with (std::list<std::string> data)
as an argument
Click to expand...
Click to expand...

Just replace
std::sort( Data.begin(), Data.end(); CILessthan );
with
Data.sort( CILessthan );
Click to expand...
As long as it's a list and not a vector.- Hide quoted text -
Click to expand...

Its not working I want Data to be of type " std::list<std::string>
Data;"

--------

Please don't send questions to my e-mail, post them here.

In this program if you replace every occurance of "vector" with "list",
change
std::sort( Data.begin(), Data.end(); CILessthan );
with
Data.sort( CILessthan );

and compile it should run fine.- Hide quoted text -

- Show quoted text -
Click to expand...


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

#include <list>
#include <iostream>
using namespace std ;
typedef list<string> VR_STRINGList;
bool CILessthan( std::list<std::string>::iterator Elem1,
std::list<std::string>::iterator Elem2 )
{
//std::list<std::string> ::iterator i;
int i;
int arrayLength = Elem1->length();
for ( i = 0; i < arrayLength; ++i )
{
if ( strcmp(Elem1->c_str(),Elem2->c_str())<=0 )
return true;
else if ( strcmp(Elem1->c_str(), Elem2->c_str())>0)
return false;
}


// Equal up to this point, but one may be longer
if ( Elem1->length() < Elem2->length())
return true;


return false;



}

void ShowData( const std::list<std::string>& Data )
{
for ( std::list<std::string>::const_iterator it = Data.begin();
it != Data.end(); ++it )
std::cout << (*it) << "\n";


}

int main()
{
std::list<std::string> Data;
Data.push_back( "ABC" );
Data.push_back( "abc" );
Data.push_back( "BBC" );
std::cout << "Before sort:\n";
ShowData( Data );


// std::sort( Data.begin(), Data.end() );
std::cout << "\nAfter sort:\n";
ShowData( Data );

// std::sort( Data.begin(), Data.end(), CILessthan );
Data.sort(CILessthan);
std::cout << "\nAfter Case Insensitive sort:\n";
ShowData( Data );


std::string wait;
std::getline( std::cin, wait );


}
I have done changes above for list but still getting error
 
A

aparnakakkar2003

news:[email protected]...
Click to expand...
can any one tell me if I give the followiing string in input:
ABC
abc
BBC
then how I can get
ABC
abc
BBC
or
abc
ABC
BBC
as my output usiing quicksort.
Well, this doesn't use quicksort but std::sort which is O( N log N ).
Output is:
Before sort:
ABC
abc
BBC
ABCD
aB
After sort:
ABC
ABCD
BBC
aB
abc
After Case Insensitive sort:
aB
ABC
abc
ABCD
BBC
There may be a better/faster algorithm for the case insensitve
comparing
of
std::strings. I just did this one rather quickly.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
bool CILessthan( const std::string Elem1, const std::string Elem2 )
{
for ( std::size_t i = 0; i < Elem1.length(); ++i )
{
if ( std::tolower( Elem1 ) < std::tolower( Elem2 ) )
return true;
else if ( std::tolower( Elem1 ) > std::tolower( Elem2 ) )
return false;
}
// Equal up to this point, but one may be longer
if ( Elem1.length() < Elem2.length() )
return true;
return false;
}
void ShowData( const std::vector<std::string>& Data )
{
for ( std::vector<std::string>::const_iterator it = Data.begin();
it
!=
Data.end(); ++it )
std::cout << (*it) << "\n";
}
int main()
{
std::vector<std::string> Data;
Data.push_back( "ABC" );
Data.push_back( "abc" );
Data.push_back( "BBC" );
Data.push_back( "ABCD" );
Data.push_back( "aB" );
std::cout << "Before sort:\n";
ShowData( Data );
std::sort( Data.begin(), Data.end() );
std::cout << "\nAfter sort:\n";
ShowData( Data );
std::sort( Data.begin(), Data.end(), CILessthan );
std::cout << "\nAfter Case Insensitive sort:\n";
ShowData( Data );
std::string wait;
std::getline( std::cin, wait );
}- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
please tell me how is it possible with (std::list<std::string> data)
as an argument
Click to expand...
Click to expand...

Just replace
std::sort( Data.begin(), Data.end(); CILessthan );
with
Data.sort( CILessthan );
Click to expand...
As long as it's a list and not a vector.- Hide quoted text -
Click to expand...

Its not working I want Data to be of type " std::list<std::string>
Data;"

--------

Please don't send questions to my e-mail, post them here.

In this program if you replace every occurance of "vector" with "list",
change
std::sort( Data.begin(), Data.end(); CILessthan );
with
Data.sort( CILessthan );

and compile it should run fine.- Hide quoted text -

- Show quoted text -
Click to expand...


Thanks,its working fine.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Parallel Quicksort 1.0 is here. 1
Subclassing std::string confusion? 2
Hello everyone 0
Inexplicable timings 1
How can I fix my pattern coding error in c++ 0
Bad use of stringstream temporary? 20
quicksort 8
Why is it printing ABC 4

Members online

No members online now.
Total: 45 (members: 0, guests: 45)
Robots: 92

Forum statistics

Threads
473,754
Messages
2,569,521
Members
44,995
Latest member
PinupduzSap

Latest Threads

Top