mt_qsort.c
2.31 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
/*
=============================================================================
Copyright (C) 1997-1999 NINTENDO Co.,Ltd.
$RCSfile: mt_qsort.c,v $
$Revision: 1.1.1.1 $
$Date: 2002/10/30 02:07:09 $
=============================================================================
関数名：mt_qsort
-----------------------------------------------------------------------------
書式： #include <stdlib.h>
void mt_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 void _mt_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 _mt_qsort(void *base, size_t num, size_t width,
int (*compare)(const void *, const void *), char **w)
{
int a, i;
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;
_mt_qsort_swap(p1, *w, width);
}
_mt_qsort_swap(p1, p2, width);
p1 = *w;
}
p2 += width;
}
a = ((int)(*w - (char *)base)/width)+1;
*w = p1;
if (a>1) _mt_qsort(base, a, width, compare, w);
*w = p1;
*w += width;
a = num-a;
if (a>1) _mt_qsort(*w, a, width, compare, w);
}
void mt_qsort(void *base, size_t num, size_t width,
int (*compare)(const void *, const void *))
{
char *w ;
w = base;
_mt_qsort(base, num, width, compare, &w);
}