1 /* $Id$
2 * Quick sort algorythm for integer array.
3 *
4 * HUSKYLIB: common defines, types and functions for HUSKY
5 *
6 * This is part of The HUSKY Fidonet Software project:
7 * see http://husky.sourceforge.net for details
8 *
9 *
10 * HUSKYLIB is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU Lesser General Public
12 * License as published by the Free Software Foundation; either
13 * version 2 of the License, or (at your option) any later version.
14 *
15 * HUSKYLIB is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * General Public License for more details.
19 *
20 * You should have received a copy of the GNU Lesser General Public
21 * License along with this library; see file COPYING. If not, write to the
22 * Free Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 *
24 * See also http://www.gnu.org, license may be found here.
25 */
26
27 #include <stddef.h>
28 #include "compiler.h"
29
30 #define DLLEXPORT
31 #include <huskylib.h>
32
33
34 #define NUM sizeof(array)/sizeof(array[0])
35 #define SWAP(a,b,s) s=a; a=b; b=s;
36
iqksort(int * p_lo,int * p_hi)37 static void _fast iqksort(int *p_lo, int *p_hi)
38 {
39 int *p_mid, *p_i, *p_lastlo, tmp;
40
41 p_mid = p_lo + (((int)(p_hi - p_lo)) / 2);
42
43 SWAP(*p_lo, *p_mid, tmp);
44
45 p_lastlo = p_lo;
46
47 for (p_i = p_lo + 1; p_i <= p_hi; ++p_i)
48 {
49 if (*p_lo > *p_i)
50 {
51 ++p_lastlo;
52 SWAP(*p_lastlo, *p_i, tmp);
53 }
54 }
55
56 SWAP(*p_lo, *p_lastlo, tmp);
57
58 if (p_lo < p_lastlo && p_lo < p_lastlo - 1)
59 {
60 iqksort(p_lo, p_lastlo - 1);
61 }
62
63 if (p_lastlo + 1 < p_hi)
64 {
65 iqksort(p_lastlo + 1, p_hi);
66 }
67 }
68
qksort(int a[],size_t n)69 void _fast qksort(int a[], size_t n)
70 {
71 if (n > 1)
72 {
73 iqksort(a, &a[n - 1]);
74 }
75 }
76