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