Adapting quicksort function for strings

[Biff123]

I managed to get a quicksort function to sort the numbers in a dynamically allocated array of structs,

struct Contact {
	char first[maxstring];
	char second[maxstring];
	int number;
};	
//and the dynamically allocated array,
Contact *person = new Contact[numberofcontacts];

//The quicksort function I used to sort numbers is:
void Quicksortnumber(Contact *person, int left, int right) {
	int L = left; 
	int R = right;
	int pivot = person[(left + right) / 2].number;																							//partition
	while (L <= R) {
		while (person[L].number < pivot){
			L++;
		}
		while (person[R].number > pivot){
			R--;
		}
		if (L <= R) {
			swap(person[L], person[R]);
			L++;
			R--;
		}
	}																						//recursion to complete sort
	if (left < R){
	Quicksortnumber(person, left, R);
	}
	if (L < right){
	Quicksortnumber(person, L, right);
	}
}	
/*This works fine for the integers I then tried to adapt this to work for the "first" member of the structure*/

void Quicksortfirst(Contact *person, int left, int right) {
	int L = left; 
	int	R = right;
	char pivot[maxstring];
	strcpy(pivot, person[(left+right)/2].first);
	while(L <= R) {
		int diff1 = strcomp(person[L].first, pivot);
		while (diff1<0){
			L++;
		}																																//scrolls from left to right
		int diff2 = strcomp(person[R].first,pivot);
		while (diff2>0){
			R--;																														//scrolls from right to left
		}
		if (L <= R) {
			swap(person[L], person[R]);
			L++;
			R--;
		}																																//swaps structs
	}																																	//recursion to complete sort
	if (left < R){
	Quicksortfirst(person, left, R);
	}																																	//repeats for lower part of split array
	if (L < right){
	Quicksortfirst(person, L, right);
	}																																	//repeats for higher part of split array
}

When I debug this, no errors are produced but when I build the code and select it to sort by first name the compiler seems to stall. I cant understand why this wouldn't work and without an error message I cant guess where it's going wrong.
Thanks for any help.

[Narue]

Look closely at these two loops and find the difference (aside from int vs string):

while (person[L].number < pivot){
    L++;
}

int diff1 = strcomp(person[L].first, pivot);

while (diff1<0){
    L++;
}

If you didn't see it, when does diff1 change inside the loop?

[Biff123]

Look closely at these two loops and find the difference (aside from int vs string):

while (person[L].number < pivot){
    L++;
}

int diff1 = strcomp(person[L].first, pivot);

while (diff1<0){
    L++;
}

If you didn't see it, when does diff1 change inside the loop?

I made that change to my Quicksortfirst function so now it reads:

void Quicksortfirst(Contact *person, int left, int right) {
	int L = left; 
	int	R = right;
	char pivot[maxstring];
	stringcopy(pivot, person[(left+right)/2].first);
	while(L <= R) {
		while (strcomp(person[L].first,pivot)<0){
			L++;
		}
                  while (strcomp(person[R].first,pivot)>0){
			R--;		}
		if (L <= R) {
			swap(person[L], person[R]);
			L++;
			R--;
		}						//swaps structs
	}														//recursion to complete sort
	if (left < R){
	Quicksortfirst(person, left, R);
	}														//repeats for lower part of split array
	if (L < right){
	Quicksortfirst(person, L, right);
	}
}

I still get the same kind of error when I compile

[Narue]

I still get the same kind of error when I compile

The error being that the sort still hangs? Because you explicitly stated before that there were no compilation errors or warnings. Assuming strcomp() is equivalent to the standard strcmp(), this works fine for a few simple tests:

void Quicksortfirst(Contact *person, int left, int right)
{
    int L = left;
    int	R = right;
    char pivot[maxstring];
    strcpy(pivot, person[(left+right)/2].first);
    while(L <= R) {
        while (strcmp(person[L].first, pivot)<0) {
            L++;
        }
        while (strcmp(person[R].first,pivot)>0) {
            R--;
        }
        if (L <= R) {
            swap(person[L], person[R]);
            L++;
            R--;
        }
    }
    if (left < R) {
        Quicksortfirst(person, left, R);
    }
    if (L < right) {
        Quicksortfirst(person, L, right);
    }
}

[Biff123]

The error being that the sort still hangs? Because you explicitly stated before that there were no compilation errors or warnings. Assuming strcomp() is equivalent to the standard strcmp(), this works fine for a few simple tests:

void Quicksortfirst(Contact *person, int left, int right)
{
    int L = left;
    int	R = right;
    char pivot[maxstring];
    strcpy(pivot, person[(left+right)/2].first);
    while(L <= R) {
        while (strcmp(person[L].first, pivot)<0) {
            L++;
        }
        while (strcmp(person[R].first,pivot)>0) {
            R--;
        }
        if (L <= R) {
            swap(person[L], person[R]);
            L++;
            R--;
        }
    }
    if (left < R) {
        Quicksortfirst(person, left, R);
    }
    if (L < right) {
        Quicksortfirst(person, L, right);
    }
}

Ye the only error being that the compiler stalls or hangs. Thanks for your help.

[Narue]

Ye the only error being that the compiler stalls or hangs. Thanks for your help.

OK then, post a complete test program that exhibits the problem, including whatever test input you're using, because I cannot reproduce it.