Skip to content

Instantly share code, notes, and snippets.

@vo
Created March 13, 2014 21:42
Show Gist options
  • Save vo/9537566 to your computer and use it in GitHub Desktop.
Save vo/9537566 to your computer and use it in GitHub Desktop.
Simple In-Place Quicksort in C (Just programming practice)
#include <cstdio>
#include <cstdlib>
#include <ctime>
void sort(int * a, size_t n) {
if (n < 2)
return;
int p = a[n/2];
int *l = a;
int *r = a + n-1;
while (l <= r) {
if (*l < p)
l++;
else if (*r > p)
r--;
else {
int t = *l;
*l++ = *r;
*r-- = t;
}
}
sort(a, r - a + 1);
sort(l, a + n - l);
}
int main() {
const size_t N = 20;
int a[N];
srand(time(0));
// create a array of N random numnbers
for (size_t i = 0; i < N; ++i)
a[i] = rand() % 100;
// print the array
printf("original: ");
for (size_t i = 0; i < N; ++i)
printf("%d ", a[i]);
putchar('\n');
// sort the array
sort(a, N);
// print the array again
printf("sorted: ");
for (size_t i = 0; i < N; ++i)
printf("%d ", a[i]);
putchar('\n');
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment