Scribd
Upload
5 views1 page

C Quick Sort and String Permutation

The document contains a C program that implements a quick sort algorithm and processes multiple test cases to find the next lexicographical permutation of a given string. If no such permutation exists, it outputs 'no answer'. The program reads input, manipulates the string accordingly, and prints the result for each test case.

Uploaded by

msigf1810
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
5 views1 page

C Quick Sort and String Permutation

The document contains a C program that implements a quick sort algorithm and processes multiple test cases to find the next lexicographical permutation of a given string. If no such permutation exists, it outputs 'no answer'. The program reads input, manipulates the string accordingly, and prints the result for each test case.

Uploaded by

msigf1810
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

#include <stdbool.

h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
void quick_sort (char *a, int n) {
if (n < 2)
return;
char p = a[n / 2];
char *l = a;
char *r = a + n - 1;
while (l <= r) {
if (*l < p) {
l++;
}
else if (*r > p) {
r--;
}
else {
char t = *l;
*l = *r;
*r = t;
l++;
r--;
}
}
quick_sort(a, r - a + 1);
quick_sort(l, a + n - l);
}
int main(int argc, char *argv[])
{
int T;
scanf("%u", &T);
for (int t = 0; t < T; t++)
{
char s[101];
scanf("%s", s);
int sl = strlen(s);
for (int i = sl - 2; i >= 0; i--)
{
for (int j = sl - 1; j > i; j--)
{
if (s[i] < s[j])
{
char c = s[i];
s[i] = s[j];
s[j] = c;
quick_sort(s + i + 1, sl - i - 1);
goto found;
}
}
}
strcpy(s, "no answer");
found:
printf("%s\n", s);
}
return 0;
}

You might also like