Yet Another eXchange Tool  0.9.0
mergesort.c
Go to the documentation of this file.
1 
12 /*
13  * Keywords:
14  * Maintainer: Jörg Behrens <behrens@dkrz.de>
15  * Moritz Hanke <hanke@dkrz.de>
16  * Thomas Jahns <jahns@dkrz.de>
17  * URL: https://doc.redmine.dkrz.de/yaxt/html/
18  *
19  * Redistribution and use in source and binary forms, with or without
20  * modification, are permitted provided that the following conditions are
21  * met:
22  *
23  * Redistributions of source code must retain the above copyright notice,
24  * this list of conditions and the following disclaimer.
25  *
26  * Redistributions in binary form must reproduce the above copyright
27  * notice, this list of conditions and the following disclaimer in the
28  * documentation and/or other materials provided with the distribution.
29  *
30  * Neither the name of the DKRZ GmbH nor the names of its contributors
31  * may be used to endorse or promote products derived from this software
32  * without specific prior written permission.
33  *
34  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
35  * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
36  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
37  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
38  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
39  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
40  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
41  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
42  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
43  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
44  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
45  */
46 #ifdef HAVE_CONFIG_H
47 #include <config.h>
48 #endif
49 
50 #include <stdlib.h>
51 #include <stdio.h>
52 
53 #include "xt/quicksort.h"
54 #include "xt/mergesort.h"
55 
56 static void insertionsort_idxpos(idxpos_type *w, size_t n);
57 static void insertionsort_index(Xt_int *val, int n, int *pos, int reset_pos);
58 
59 
60 static void insertionsort_idxpos(idxpos_type *w, size_t n) {
61 
62  size_t i, j;
63  for(i = 1; i < n; i++) {
64 
65  idxpos_type tw = w[i];
66 
67  for(j = i; j > 0 && w[j-1].idx > tw.idx; j--) {
68  w[j] = w[j-1];
69  }
70  w[j] = tw;
71  }
72 }
73 
74 static void insertionsort_index(Xt_int *val, int n, int *pos, int reset_pos) {
75 
76  int i, j;
77 
78  if (pos != NULL) {
79 
80  if (reset_pos) {
81  for(i = 0; i < n; i++) {
82  pos[i]=i;
83  }
84  }
85 
86  for(i = 1; i < n; i++) {
87 
88  Xt_int tv = val[i];
89  int tp = pos[i];
90 
91  for(j = i; j > 0 && val[j-1] > tv; j--) {
92  val[j] = val[j-1];
93  pos[j] = pos[j-1];
94  }
95 
96  val[j] = tv;
97  pos[j] = tp;
98  }
99 
100  } else {
101 
102  for(i = 1; i < n; i++) {
103 
104  Xt_int tv = val[i];
105 
106  for(j = i; j > 0 && val[j-1] > tv; j--) {
107  val[j] = val[j-1];
108  }
109 
110  val[j] = tv;
111  }
112 
113  }
114 
115 }
116 
117 static inline void
118 my_merge_idxpos(idxpos_type * restrict v, idxpos_type * restrict w, size_t lb1, size_t ub1, size_t lb2, size_t ub2) {
119 
120  size_t p = lb1;
121  size_t i1 = lb1;
122  size_t i2 = lb2;
123 
124  while(i1<=ub1 && i2<=ub2) {
125  if (v[i1].idx <= v[i2].idx) {
126  w[p]=v[i1];
127  i1++;
128  } else {
129  w[p]=v[i2];
130  i2++;
131  }
132  p++;
133  }
134  while(i1<=ub1) {
135  w[p]=v[i1];
136  i1++;
137  p++;
138  }
139  while(i2<=ub2) {
140  w[p]=v[i2];
141  i2++;
142  p++;
143  }
144 }
145 
146 static void
147 my_mergesort_idxpos(idxpos_type * restrict v, idxpos_type * restrict w, size_t lb, size_t ub)
148 {
149 
150  size_t n = ub - lb + 1;
151  if (n<2) return;
152 
153  if (n<9) {
154  insertionsort_idxpos(&v[lb],n);
155  return;
156  }
157 
158  size_t m = n/4;
159 
160  // 4-way subsort:
161  size_t lb1 = lb;
162  size_t ub1 = lb1 + m - 1;
163 
164  size_t lb2 = ub1+1;
165  size_t ub2 = lb2 + m - 1;
166 
167  size_t lb3 = ub2+1;
168  size_t ub3 = lb3 + m - 1;
169 
170  size_t lb4 = ub3+1;
171  size_t ub4 = ub;
172 
173  my_mergesort_idxpos(v, w, lb1, ub1);
174  my_mergesort_idxpos(v, w, lb2, ub2);
175  my_mergesort_idxpos(v, w, lb3, ub3);
176  my_mergesort_idxpos(v, w, lb4, ub4);
177 
178  // 2 x 2-way merge v -> w
179  my_merge_idxpos(v, w, lb1, ub1, lb2, ub2);
180  my_merge_idxpos(v, w, lb3, ub3, lb4, ub4);
181  // final merge: w -> v
182  my_merge_idxpos(w, v, lb1, ub2, lb3, ub4);
183 
184 }
185 
186 void xt_mergesort_idxpos(idxpos_type * restrict v, size_t n)
187 {
188 
189  idxpos_type *w = malloc(n * sizeof(w[0]));
190  my_mergesort_idxpos(v, w, 0, n-1);
191  free(w);
192 
193 }
194 
195 void xt_mergesort_index(Xt_int *val, int n, int *pos, int reset_pos) {
196 
197  // insertion sort for few elements:
198  if (n<9) {
199  insertionsort_index(val,n,pos,reset_pos);
200  return;
201  }
202 
203  idxpos_type *v;
204  idxpos_type *w;
205 
206  v = malloc((size_t)n * sizeof(v[0]));
207  w = malloc((size_t)n * sizeof(w[0]));
208 
209  if (reset_pos || pos == NULL) {
210  for(int i=0; i<n; i++) {
211  v[i].idx = val[i];
212  v[i].pos = i;
213  }
214  } else {
215  for(int i=0; i<n; i++) {
216  v[i].idx = val[i];
217  v[i].pos = pos[i];
218  }
219  }
220 
221  my_mergesort_idxpos(v,w, 0, (size_t)n-1);
222  if (pos) {
223  for(int i=0; i<n; i++) {
224  val[i] = v[i].idx;
225  pos[i] = v[i].pos;
226  }
227  } else {
228  for(int i=0; i<n; i++) {
229  val[i] = v[i].idx;
230  }
231  }
232 
233  free(w);
234  free(v);
235 }
236 
237 
238 /*
239  * Local Variables:
240  * c-basic-offset: 2
241  * coding: utf-8
242  * indent-tabs-mode: nil
243  * show-trailing-whitespace: t
244  * require-trailing-newline: t
245  * End:
246  */
void xt_mergesort_index(Xt_int *val, int n, int *pos, int reset_pos)
Definition: mergesort.c:195
static void insertionsort_idxpos(idxpos_type *w, size_t n)
Definition: mergesort.c:60
static void my_merge_idxpos(idxpos_type *restrict v, idxpos_type *restrict w, size_t lb1, size_t ub1, size_t lb2, size_t ub2)
Definition: mergesort.c:118
static void my_mergesort_idxpos(idxpos_type *restrict v, idxpos_type *restrict w, size_t lb, size_t ub)
Definition: mergesort.c:147
void xt_mergesort_idxpos(idxpos_type *restrict v, size_t n)
Definition: mergesort.c:186
static void insertionsort_index(Xt_int *val, int n, int *pos, int reset_pos)
Definition: mergesort.c:74
merge sort declaration
integer, parameter, public i2
Definition: xt_core_f.f90:58
quicksort declaration
XT_INT Xt_int
Definition: xt_core.h:68