include <iostream>

using namespace std;

int random_in_range(int a, int b) {
        return a+random()%(b-a+1);
}

void swap(string &a, string &b) {
        string temp = a;
        a = b;
        b = temp;
}

int partition(string A[], int begin, int end) {
        int PivPos = random_in_range(begin,end);
        int P = begin, Q = end;

        while (true) {
                while (A[P]<=A[PivPos] && P<=end)
                        P++;
                while (A[Q]>=A[PivPos] && Q>=begin)
                        Q--;
                if (P<Q) {
                        swap(A[P],A[Q]);
                        P++;
                        Q--;
                }
                else {
                        if (P<=PivPos) {
                                swap(A[P],A[PivPos]);
                                P++;
                        }
                        else if (Q>=PivPos) {
                                swap(A[Q],A[PivPos]);
                                Q++;
                        }
                        break;
                }
        }

        return PivPos;
}

void quicksort(string A[], int begin, int end) {
        if (end>begin) {    
                int piv = partition(A,begin,end);
                quicksort(A,begin,piv);
                quicksort(A,piv+1,end);
        }               
}                               
                                    
void main() {            
        const int size = 10;
        string x[size] = {"aa", "bb", "cc", "ddd", "ff", "ee", "ab", "gg", "dd", "zz"};
        for (int i=0; i<size; i++) {
                cout << x[i] << " ";
        }               
        cout << "\n";
         
        quicksort(x,0,size-1);
        
        for (int i=0; i<size; i++) {
                cout << x[i] << " ";
        }
        cout << "\n";
}