qsort.c
2.27 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*
=============================================================================
Copyright (C) 1997-1999 NINTENDO Co.,Ltd.
$RCSfile: qsort.c,v $
$Revision: 1.1.1.1 $
$Date: 2002/10/30 02:07:09 $
=============================================================================
関数名：qsort
-----------------------------------------------------------------------------
書式： #include <stdlib.h>
void qsort(void *base, size_t num, size_t width,
int (*compare)(const void *, const void *));
引数： base 配列を示すポインタ
num 配列の要素数
width 配列の１要素の大きさ（バイト単位）
compare 比較する関数
戻り値：なし
説明： 配列のクイックソートを行う。
引数 compareは、ユーザーが作成した比較関数のポインタ。
int compare((type *)elem1, (type *)elem2);
(type *)は任意の型。
返す値は、
0以下 elem1 は elem2より小さい
0 elem1 は elem2と等しい
0以上 elem1 は elem2より大きい
-----------------------------------------------------------------------------
*/
#include "stdlib.h"
static int i;
static char *w;
static void _qsort_swap(char *p1, char *p2, int width)
{
int k,c;
for (k = 0; k<width; k++) {
c = *p1;
*p1++ = *p2;
*p2++ = c;
}
}
static void _qsort(void *base, size_t num, size_t width,
int (*compare)(const void *, const void *))
{
int a;
char *p1, *p2;
if (num < 1) return;
p1 = p2 = base;
p2 += width;
for (i=0; i<num-1; i++) {
a = compare(p1, p2);
if (a>0) {
if (((int)(p2-p1)/width) <2) w = p2;
else {
w = p1;
w += width;
_qsort_swap(p1, w, width);
}
_qsort_swap(p1, p2, width);
p1 = w;
}
p2 += width;
}
a = ((int)(w - (char *)base)/width)+1;
w = p1;
if (a>1) _qsort(base, a, width, compare);
w = p1;
w += width;
a = num-a;
if (a>1) _qsort(w, a, width, compare);
}
void qsort(void *base, size_t num, size_t width,
int (*compare)(const void *, const void *))
{
w = base;
_qsort(base, num, width, compare);
}