1/* 2 * Copyright 2014, NICTA 3 * 4 * This software may be distributed and modified according to the terms of 5 * the BSD 2-Clause license. Note that NO WARRANTY is provided. 6 * See "LICENSE_BSD2.txt" for details. 7 * 8 * @TAG(NICTA_BSD) 9 */ 10#ifdef TEST 11#include <stdio.h> 12#include <stdlib.h> 13#endif 14 15unsigned long partition(unsigned int *a, unsigned long n) 16{ 17 // assume n != 0 18 19 // unsigned int pivot = a[0]; 20 unsigned long pivot_idx = 0; // stupid pivot choice for now 21 22 for (unsigned long i = 1; i < n; i++) { 23 if (a[i] < a[pivot_idx]) { 24 unsigned int pivot = a[pivot_idx]; 25 a[pivot_idx] = a[i]; 26 pivot_idx++; 27 a[i] = a[pivot_idx]; 28 a[pivot_idx] = pivot; 29 // pivot = pivot; // hack to get AutoCorres to recognise "pivot" in the loop body 30 } 31 } 32 33 return pivot_idx; 34} 35 36void quicksort(unsigned int *a, unsigned long n) 37{ 38 if (n > 1) { 39 unsigned long pivot_idx = partition(a, n); 40 quicksort(a, pivot_idx); 41 quicksort(a + pivot_idx + 1, n - pivot_idx - 1); 42 } 43} 44 45#ifdef TEST 46 47int main(void) 48{ 49 unsigned int sz; 50 scanf("%u", &sz); 51 unsigned int *a = malloc(sz * sizeof(unsigned int)); 52 for (unsigned int i = 0; i < sz; i++) { 53 scanf("%u", a+i); 54 } 55 56 quicksort(a, sz); 57 58 for (unsigned int i = 0; i < sz; i++) { 59 if (i) putchar(' '); 60 printf("%u", a[i]); 61 } 62 printf("\n"); 63 64 return 0; 65} 66 67#endif 68