Из пузырька в квиксорт. с++

[discorsa]

Задание - алфавитная сортировка строки ( с Class String). Ну, сделала через пузырёк, но execution time же - убийственен. Надо переделать в квиксорт, но что-то сооовсем не соображу как. Ниже имеющийся рабочий код, пузырьком. Помогите, пожалуйста, с void sort ().
/единственный мой класс программирования (кроме ассемблера%) ), а я застряла.

using namespace std;

void sort ( String *a, int n )
{
int changed;
String temp;
do {
changed = 0;
for ( int i = 0; i < n - 1; i++ ) {
if ( a[i+1] < a[i] ) {
temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
changed = 1;
}
}
} while ( changed );
}

void input ( String *a, int limit, int &i )
//value of i will be passed out as size
{
static char buffer[100];
cout << "\nenter data:";
for ( i = 0; i < limit; i++ )
if ( scanf( "%s", buffer ) == EOF )
break;
else
a[i] = String ( buffer );
}

void output( String *a, int size )
{

cout << "\nlist : ";
for ( int i = 0; i < size; i++ )
a[i].prints();
//cout << a[i];
cout << endl;
}

int main()
{
const int max = 10;
String list[max];

int size = 0;

String x, y;
input ( list, max, size );
sort ( list, size );
output ( list, size );

return 0;
}

#ifndef STR_H
#define STR_H
#include

using namespace std;

class String {
protected:
char *str;
public:
//constructors
String(); //create an empty string
~String(); // cleanup
String ( char *init ); //initializes str to string init
int length(); //returns length of this string
void prints(); //prints this string
bool operator < ( String &s ); //if this String < String s returns true
//else false
int find_pat( String pattern );//returns an index i such that pattern
//matches the substring of this string that
//begins at position i, returns -1 if no match
void operator << ( ostream &out );
};

#endif

#include "str.h"

String::String()
{
str = new char[1]; //points to new node
*str = 0; //initializes to NULL string
}

String::String( char *s )
{
if ( str ) delete[] str;
str = new char[ strlen( s ) + 1 ];
strcpy( str, s );
}

String::~String()
{
if ( str ) delete[] str;
}

int String::length()
{
return( strlen( str ) );
}

void String::prints()
{
cout << str << "\n";
}

bool String::operator < ( String &s )
{
return ( strcmp( str, s.str ) < 0 );
}

//ostream & String::operator << ( ostream &out )
void String::operator << ( ostream &out )
{
out << str << endl;
//return out;

[_ILYA_]

ты не могла бы оформить по лучше а то в такой мешанине просто лень даже разбиратся

[sever-42]

1. Берем опорный элемент из массива(лучше брать середину) a[i].
У нас получилось 3 подмножества - левая, правая, и середина.
=<a[i]... ...|a[i]|... ... >=a[i]
2. помещаем все элементы меньше либо равные a[i] влево от него, a элементы >= a[i]
вправо от a[i]
3. Рекурсивно сортируем подмассивы меньше опорного и больше опорного, пока колличество элементов в них > 2.