Mercurial > hg > ltpda

comparison src/ltpda_smoother/quick.c @ 0:f0afece42f48

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import.
author Daniele Nicolodi <nicolodi@science.unitn.it>
date Wed, 23 Nov 2011 19:22:13 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:f0afece42f48
1
2 #include <stdlib.h>
3 #include <stdio.h>
4
5
6
7 /* // quickSort
8 //
9 // This public-domain C implementation by Darel R. Finley.
10 //
11 // * Returns true if sort was successful, or false if the nested
12 // pivots went too deep, in which case your array will have
13 // been re-ordered, but probably not sorted correctly.
14 //
15 // * This function assumes it is called with valid parameters.
16 //
17 // * Example calls:
18 // quickSort(&myArray[0],5); // sorts elements 0, 1, 2, 3, and 4
19 // quickSort(&myArray[3],5); // sorts elements 3, 4, 5, 6, and 7*/
20
21 #define MAX_LEVELS 1000
22
23 int quickSort(double *arr, int elements)
24 {
25 double piv;
26 int beg[MAX_LEVELS], end[MAX_LEVELS];
27 int i=0;
28 int L, R;
29
30 beg[0]=0; end[0]=elements;
31 while (i>=0)
32 {
33 L=beg[i]; R=end[i]-1;
34 if (L<R)
35 {
36 piv=arr[L];
37 if (i==MAX_LEVELS-1) return -1;
38 while (L<R)
39 {
40 while (arr[R]>=piv && L<R)
41 R--;
42 if (L<R)
43 arr[L++]=arr[R];
44 while (arr[L]<=piv && L<R)
45 L++;
46 if (L<R)
47 arr[R--]=arr[L];
48 }
49 arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L;
50 }
51 else
52 {
53 i--;
54 }
55 }
56
57 return 0;
58 }