#include<iostream>
#include<ctime>
#include<string>
using namespace std;
int quick_sort_help(string &text,int left, int right, int pivot){
char val = text[pivot];
char temp;
//swap
// temp =text[pivot];
//text[pivot]= text[right];
//text[right]=temp;
//swap(&text[left],&text[right]);
int l = left;
int r = right;
int i=left;
while (i<=r)
{
while (text[i]<val)
i++;
while (text[right]>val)
r--;
if (i<=r)
{
temp=text[i];
text[i]=text[r];
text[r]=temp;
i++;
r--;
}
}
return l;
}
void quicksort(string &text,int left, int right){
if (left < right){
int pivot=(left+right)/2;
int pivottwo = quick_sort_help(text, left, right, pivot);
quicksort(text, left, pivottwo - 1);
quicksort(text, pivottwo + 1, right);
}
}
void quick_sort(string &text,int size){
quicksort(text,0,size);}
int main()
{
string text="this is a test string text,.,!";
int size = text.length();
float t1, t2;
t1 = clock();
quick_sort(text,size);
t2=clock();
cout<<text<<endl;
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGN0aW1lPgojaW5jbHVkZTxzdHJpbmc+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgoKaW50IHF1aWNrX3NvcnRfaGVscChzdHJpbmcgJnRleHQsaW50IGxlZnQsIGludCByaWdodCwgaW50IHBpdm90KXsKCgogIGNoYXIgdmFsID0gdGV4dFtwaXZvdF07CiAgY2hhciB0ZW1wOwoKICAvL3N3YXAKIC8vIHRlbXAgPXRleHRbcGl2b3RdOwogIC8vdGV4dFtwaXZvdF09IHRleHRbcmlnaHRdOwogIC8vdGV4dFtyaWdodF09dGVtcDsKCiAgLy9zd2FwKCZ0ZXh0W2xlZnRdLCZ0ZXh0W3JpZ2h0XSk7CgogIGludCBsID0gbGVmdDsKICBpbnQgciA9IHJpZ2h0OwoKICBpbnQgaT1sZWZ0OwogIHdoaWxlIChpPD1yKQogIHsKICAgICAgd2hpbGUgKHRleHRbaV08dmFsKQogICAgICAgICAgaSsrOwogICAgICB3aGlsZSAodGV4dFtyaWdodF0+dmFsKQogICAgICAgICAgci0tOwogICAgICBpZiAoaTw9cikKICAgICAgewogICAgICAgICAgdGVtcD10ZXh0W2ldOwogICAgICAgICAgdGV4dFtpXT10ZXh0W3JdOwogICAgICAgICAgdGV4dFtyXT10ZW1wOwogICAgICAgICAgaSsrOwogICAgICAgICAgci0tOwogICAgICB9CiAgfQoKCiAgcmV0dXJuIGw7CiAgICAgfQoKCnZvaWQgcXVpY2tzb3J0KHN0cmluZyAmdGV4dCxpbnQgbGVmdCwgaW50IHJpZ2h0KXsKCiAgICAgIGlmIChsZWZ0IDwgcmlnaHQpewoKICAgICAgICAgIGludCBwaXZvdD0obGVmdCtyaWdodCkvMjsKICAgICAgICAgIGludCBwaXZvdHR3byA9IHF1aWNrX3NvcnRfaGVscCh0ZXh0LCBsZWZ0LCByaWdodCwgcGl2b3QpOwogICAgICAgICAgcXVpY2tzb3J0KHRleHQsIGxlZnQsIHBpdm90dHdvIC0gMSk7CiAgICAgICAgICBxdWlja3NvcnQodGV4dCwgcGl2b3R0d28gKyAxLCByaWdodCk7CiAgICAgICAgICB9CiB9ICAKdm9pZCBxdWlja19zb3J0KHN0cmluZyAmdGV4dCxpbnQgc2l6ZSl7CiAgICAgICAgICAgICAgcXVpY2tzb3J0KHRleHQsMCxzaXplKTt9CgoKaW50IG1haW4oKQp7CgogICAgc3RyaW5nIHRleHQ9InRoaXMgaXMgYSB0ZXN0IHN0cmluZyB0ZXh0LC4sISI7CiAgICBpbnQgc2l6ZSA9IHRleHQubGVuZ3RoKCk7CiAgICBmbG9hdCB0MSwgdDI7CiAgICB0MSA9IGNsb2NrKCk7CiAgICBxdWlja19zb3J0KHRleHQsc2l6ZSk7CgogICAgdDI9Y2xvY2soKTsKICAgIGNvdXQ8PHRleHQ8PGVuZGw7CgogICAgcmV0dXJuIDA7Cn0=