David Wang David Wang -4 years ago 64
C Question

Sort a string in C with quick sort

I want to sort a string in C according to the ASCII value of each char in the string. I write a quick sort to do this. My code is as following:

#include<stdio.h>
#include<stdlib.h>
void quick_sort(char* str, int l, int r){
if(l < r){
int left = l;
int right = r;
char x = *str;
while(left < right){
while(left < right && *(str+right) > x)
right--;
if(left < right)
*(str+(left++)) = *(str+right);
while(left < right && *(str+left) < x)
left++;
if(left < right)
*(str+(right--)) = *(str+left);
}
*(str+left) = x;
quick_sort(str, l, left-1);
quick_sort(str, right+1, r);
}
}

main(){
char* str = (char*)malloc(sizeof(char)*100);
printf("please input a string: ");
scanf("%s", str);
printf("the original string is: %s\n", str);
quick_sort(str, 0, strlen(str)-1);
printf("the sorted string is: %s\n",str);
free(str);
system("pause");
}


But it can only work when the string is very short, say "bac". When the string is longer, the result is wrong. It would be helpful if anyone could give me any ideas.

Answer Source

Your partition algorithm is lossy.

When the condition is true, the following:

        if(left < right)
            *(str+(left++)) = *(str+right);

overwrites str[left]. Once this happens, the character is irreversibly lost.

The same goes for the other if.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download