Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
qsort with 3 way partitions (<T, ==T, >T)
#include <stdio.h>
void qsort3(int *X, int L, int U) {
int T, M, E, i, tmp;
if (L < U) {
T = X[L];
M = L;
E = U;
for (i = L+1; i < E; i++) {
if (X[i] < T) {
M += 1;
tmp = X[M];
X[M] = X[i];
X[i] = tmp;
} else if (X[i] == T) {
E -= 1;
X[i] = X[E];
X[E] = T;
i -= 1;
}
}
X[L] = X[M];
X[M] = T;
for (i = E; i < U; i++) {
M += 1;
X[i] = X[M];
X[M] = T;
}
qsort(X, L, M);
qsort(X, M+1, U);
}
}
int main(int argc, char *argv[]) {
int a[] = {4, 65, 4, 4, 2, -31, 0, 99, 2, 4, 83, 782, 1};
int n = sizeof a / sizeof a[0];
int i;
for (i = 0; i < n; i++)
printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
qsort3(a,0, n);
for (i = 0; i < n; i++)
printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.