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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
# Written by Aleksey Cheusov <vle@gmx.net>, public domain
#
# This awk module is a part of RunAWK distribution,
# http://sourceforge.net/projects/runawk
#
############################################################
# =head2 quicksort.awk
#
# =over 2
#
# =item I<quicksort (src_array, dest_remap, start, end)>
#
# The content of `src_array' is sorted using awk's rules for
# comparing values. Values with indices in range [start, end] are
# sorted. `src_array' array is not changed.
# Instead dest_remap array is generated such that
#
# Result:
# src_array [dest_remap [start]] <=
# <= src_array [dest_remap [start+1]] <=
# <= src_array [dest_remap [start+2]] <= ... <=
# <= src_array [dest_remap [end]]
#
# `quicksort' algorithm is used.
# Examples: see demo_quicksort and demo_quicksort2 executables
#
# =item I<quicksort_values (src_hash, dest_remap)>
#
# The same as `quicksort' described above, but hash values are sorted.
#
# Result:
# src_hash [dest_remap [1]] <=
# <= src_hash [dest_remap [2]] <=
# <= src_hash [dest_remap [3]] <= ... <=
# <= src_hash [dest_remap [count]]
#
# `count', a number of elements in `src_hash', is a return value.
# Examples: see demo_quicksort* executables.
#
# =item I<quicksort_indices (src_hash, dest_remap)>
#
# The same as `quicksort' described above, but hash indices are sorted.
#
# Result:
# dest_remap [1] <=
# <= dest_remap [2] <=
# <= dest_remap [3] <= ... <=
# <= dest_remap [count]
#
# `count', a number of elements in `src_hash', is a return value.
#
# =back
#
function __quicksort (array, index_remap, start, end,
MedIdx,Med,v,i,storeIdx)
{
if ((end - start) <= 0)
return
MedIdx = int((start+end)/2)
Med = array [index_remap [MedIdx]]
v = index_remap [end]
index_remap [end] = index_remap [MedIdx]
index_remap [MedIdx] = v
storeIdx = start
for (i=start; i < end; ++i){
if (array [index_remap [i]] < Med){
v = index_remap [i]
index_remap [i] = index_remap [storeIdx]
index_remap [storeIdx] = v
++storeIdx
}
}
v = index_remap [storeIdx]
index_remap [storeIdx] = index_remap [end]
index_remap [end] = v
__quicksort(array, index_remap, start, storeIdx-1)
__quicksort(array, index_remap, storeIdx+1, end)
}
function quicksort (array, index_remap, start, end, i)
{
for (i=start; i <= end; ++i)
index_remap [i] = i
__quicksort(array, index_remap, start, end)
}
function quicksort_values (hash, remap_idx,
array, remap, i, j, cnt)
{
cnt = 0
for (i in hash) {
++cnt
array [cnt] = hash [i]
remap [cnt] = i
}
quicksort(array, remap_idx, 1, cnt)
for (i=1; i <= cnt; ++i) {
remap_idx [i] = remap [remap_idx [i]]
}
return cnt
}
function quicksort_indices (hash, remap_idx,
array, i, cnt)
{
cnt = 0
for (i in hash) {
++cnt
array [cnt] = i
}
quicksort(array, remap_idx, 1, cnt)
for (i=1; i <= cnt; ++i) {
remap_idx [i] = array [remap_idx [i]]
}
return cnt
}
|
