Skip to content

Instantly share code, notes, and snippets.

@jtrim
Created April 3, 2011 03:03
Show Gist options
  • Select an option

  • Save jtrim/900140 to your computer and use it in GitHub Desktop.

Select an option

Save jtrim/900140 to your computer and use it in GitHub Desktop.
Implementation of quicksort in C
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define _int uint8_t
_int *quicksort(_int *arr, int size_of_arr) {
if (size_of_arr <= 1)
return arr;
_int *current_arr = arr + 1;
_int *smaller = malloc(sizeof(arr) - 1);
_int *bigger = malloc(sizeof(arr) - 1);
int smaller_count = 0;
int bigger_count = 0;
_int pivot_value = arr[0];
int i;
for (i = 0; i < size_of_arr - 1; i++) {
if (current_arr[i] <= pivot_value)
smaller[smaller_count++] = current_arr[i];
else
bigger[bigger_count++] = current_arr[i];
}
smaller = quicksort(smaller, smaller_count);
bigger = quicksort(bigger, bigger_count);
for (i = 0; i < smaller_count; i++)
arr[i] = smaller[i];
arr[i++] = pivot_value;
int m;
for (m = 0; m < bigger_count; m++)
arr[m+i] = bigger[m];
free(smaller);
smaller = NULL;
free(bigger);
bigger = NULL;
return arr;
}
int main() {
printf("Beginning quicksort thingy\n\n");
int size_of_arr = 10;
_int *arr_to_sort = malloc(size_of_arr);
arr_to_sort[0] = 3;
arr_to_sort[1] = 4;
arr_to_sort[2] = 1;
arr_to_sort[3] = 6;
arr_to_sort[4] = 2;
arr_to_sort[5] = 15;
arr_to_sort[6] = 8;
arr_to_sort[7] = 1;
arr_to_sort[8] = 3;
arr_to_sort[9] = 1;
printf( "Before sort:\n" );
int j;
for (j = 0; j < size_of_arr; j++)
printf("%i\n", (int)arr_to_sort[j]);
(void)quicksort(arr_to_sort, size_of_arr);
printf( "\nAfter sort:\n" );
for (j = 0; j < size_of_arr; j++)
printf("%i\n", arr_to_sort[j]);
free(arr_to_sort);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment