Created
April 3, 2011 03:03
-
-
Save jtrim/900140 to your computer and use it in GitHub Desktop.
Implementation of quicksort in C
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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