How to use qsort for string in C++

Question

I want to use qsort function to sort the characters in the strings using C++.

#include<iostream>
#include<string>
#include<cstdlib>

using namespace std;

int compare_str(void const *a,void const *b){
    char const *aa=(char const *)a;
    char const *bb=(char const *)b;

    if(*aa==*bb) return 0;
    else if(*aa>*bb) return 1;
    else return -1;
}
int main(){

    string str="cake";
    int len=str.length();

    qsort(str,len,sizeof(str[0]),compare_str);
    cout<<str;
    return 0;
}

But it throws :

20 42 [Error] cannot convert 'std::string {aka std::basic_string<char>}' to 'void*' for argument '1' to 'void qsort(void*, size_t, size_t, int (*)(const void*, const void*))' 

It would be great if anyone could provide an efficient way to do this.

Crouton

You know std::sort exists right? – Carmencarmena

std::sort uses algorithms like mergesort or quicksort, which are inefficient for sorting sequences like a string. Consider alternatives like radix sort, which are asymptotically optimal in the general case. – Macaroni

Answer 1

I strongly recommend the modern method of

#include <algorithm>
#include <iostream>
#include <string>

int main()
{
    std::string s("cake");

    std::sort(s.begin(), s.end());

    std::cout << s << std::endl; // Prints "acek".

    return 0;
}

Plus, using std::sort over qsort allows the compiler to optimize better, so it's a win-win...

Boomkin

Answer 2

Your comparator for qsort expects C strings, not C++ std::strings. You should either declare str to be char str[]

char str[] = "cake";
qsort(str, strlen(cake), sizeof(char), compare_str); // Consider renaming to compare_char

or (better) use std::sort:

string str = "cake";
sort(str.begin(), str.end());

Prophetic

Your example with vector<string> str will sort the strings in the vector, not the individual characters in the strings, correct? It's a little unclear whether he is just sorting one string or many... – Boomkin

@RyanMcK Ah, you're right, it looks like the OP wants to sort individual characters! – Prophetic

@dasblinkenlight -- As you know sizeof(char) is one by definition. Further, the number of characters in str is not 3. Better to write your call to qsort as qsort(str, strlen(str), 1, compare_char) YMMV. – Occlude

@HappyGreenKidNaps Right, 3 was there from my prior edit - I put strlen back. Keeping sizeof in is OK with me for descriptiveness. Thanks! – Prophetic

Answer 3

If you really want to do this, just pass a pointer to the string's contents:

qsort(str.c_str(),len,sizeof(str[0]),compare_str);

That said, you really should consider using the functions provided in the STL rather than those from the old C library...

Cagliari

s/STL/Standard Library/ – Gerrald

If you're going to go that route, probably better to use str.c_str(). But as many others have said, std::sort is the best choice. – Goshawk

Never mind, asker wanted to sort the string in place. My mistake. Nevertheless, is &str[0] guaranteed to work? – Goshawk

@Goshawk -- c_str() returns a pointer to const char. Passing it to qsort is UB. – Occlude

Yeah, realized my mistake shortly after saying that. Main thing I was getting at is whether the &str[0] would work, though I suppose given that the code is using str.length() rather than strlen(&str[0]) it should be ok. – Goshawk

Come to think of it, the bytes may not be guaranteed to be null terminated without calling std::string::c_str(). Thanks for raising the point, Joel. – Cagliari

Answer 4

You should use the function sort() under the header <algorithm>. This function is very flexible and you can use it in different manner. For sorting as you wish in question you can just write:

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int main()
{
string s="cake";

sort(s.begin(), s.end());

cout << s << endl;

return 0;
}

//output: acek

again by using sort() we can implement it in a range. If you want to sort first two element , the code will be

sort(s.begin(), s.begin()+2);

for above code the output will be

//output: acke

so if we want to sort first n element then we can write

sort(s.begin,s.begin()+n);

we can also modify the sort function. In that case we have to pass three parameter instead of two. The third parameter will be a functions which returns a bool value.For example , if we want to sort in descending order then our code will be like this

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

bool desc(char i, char j)
{
    return i>j;
}

int main()
{
    string s="cake";

    sort(s.begin(), s.end(),desc);

    cout << s << endl;

    return 0;
}

//output: keca

Showroom

Answer 5

#include<iostream>
#include<string>
#include<cstdlib>

using namespace std;

int compare_str(void const *a,void const *b){
    char const *aa=(char const *)a;
    char const *bb=(char const *)b;

    if(*aa==*bb) return 0;
    else if(*aa>*bb) return 1;
    else return -1;
}
int main(){

    string str="cake";
    int len=str.length();

    qsort(const_cast<char*>(str.c_str()),len,sizeof(str[0]),compare_str);
    cout<<str<<endl;
    return 0;
}

Torsibility