IT++ Logo
sort.h
Go to the documentation of this file.
1
29#ifndef SORT_H
30#define SORT_H
31
32#include <itpp/base/vec.h>
35
36
37namespace itpp
38{
39
48enum SORTING_METHOD { INTROSORT = 0, QUICKSORT = 1, HEAPSORT = 2,
49 INSERTSORT = 3
50 };
51
98template<class T>
99class Sort
100{
101public:
103 Sort(SORTING_METHOD method = INTROSORT): sort_method(method) {}
104
106 void set_method(SORTING_METHOD method) { sort_method = method; }
107
109 SORTING_METHOD get_method() const { return sort_method; }
110
118 void sort(int low, int high, Vec<T> &data);
119
127 ivec sort_index(int low, int high, const Vec<T> &data);
128
142 void intro_sort(int low, int high, int max_depth, Vec<T> &data);
143
157 ivec intro_sort_index(int low, int high, int max_depth,
158 const Vec<T> &data);
159
160private:
161 SORTING_METHOD sort_method;
162
163 void IntroSort(int low, int high, int max_depth, T data[]);
164 void IntroSort_Index(int low, int high, int max_depth, int indexlist[],
165 const T data[]);
166
167 void QuickSort(int low, int high, T data[]);
168 void QuickSort_Index(int low, int high, int indexlist[], const T data[]);
169
170 void HeapSort(int low, int high, T data[]);
171 void HeapSort_Index(int low, int high, int indexlist[], const T data[]);
172
173 void InsertSort(int low, int high, T data[]);
174 void InsertSort_Index(int low, int high, int indexlist[], const T data[]);
175};
176
177
186template<class T>
187void sort(Vec<T> &data, SORTING_METHOD method = INTROSORT)
188{
189 Sort<T> s(method);
190 s.sort(0, data.size() - 1, data);
191}
192
202template<class T>
203ivec sort_index(const Vec<T> &data, SORTING_METHOD method = INTROSORT)
204{
205 Sort<T> s(method);
206 return s.sort_index(0, data.size() - 1, data);
207}
208
209
210// ----------------------------------------------------------------------
211// Public functions for various sorting methods
212// ----------------------------------------------------------------------
213
214template<class T>
215void Sort<T>::sort(int low, int high, Vec<T> &data)
216{
217 int N = data.size();
218 // Nothing to sort if data vector has only one or zero elements
219 if (N < 2)
220 return;
221
222 it_assert((low >= 0) && (high > low) && (high < N), "Sort::sort(): "
223 "low or high out of bounds");
224
225 switch (sort_method) {
226 case INTROSORT:
227 IntroSort(low, high, levels2bits(N), data._data());
228 break;
229 case QUICKSORT:
230 QuickSort(low, high, data._data());
231 break;
232 case HEAPSORT:
233 HeapSort(low, high, data._data());
234 break;
235 case INSERTSORT:
236 InsertSort(low, high, data._data());
237 break;
238 default:
239 it_error("Sort<T>::sort(): Unknown sorting method");
240 }
241}
242
243
244template<class T>
245ivec Sort<T>::sort_index(int low, int high, const Vec<T> &data)
246{
247 int N = data.size();
248 // Nothing to sort if data vector has only one or zero elements
249 if (N == 1)
250 return ivec("0");
251 else if (N == 0)
252 return ivec();
253
254 it_assert((low >= 0) && (high > low) && (high < N), "Sort::sort(): "
255 "low or high out of bounds");
256
257 ivec indexlist(N);
258 for (int i = 0; i < N; ++i) {
259 indexlist(i) = i;
260 }
261
262 switch (sort_method) {
263 case INTROSORT:
264 IntroSort_Index(low, high, levels2bits(N), indexlist._data(),
265 data._data());
266 break;
267 case QUICKSORT:
268 QuickSort_Index(low, high, indexlist._data(), data._data());
269 break;
270 case HEAPSORT:
271 HeapSort_Index(low, high, indexlist._data(), data._data());
272 break;
273 case INSERTSORT:
274 InsertSort_Index(low, high, indexlist._data(), data._data());
275 break;
276 default:
277 it_error("Sort<T>::sort_index(): Unknown sorting method");
278 }
279
280 return indexlist;
281}
282
283
284// INTRO SORT
285template<class T>
286void Sort<T>::intro_sort(int low, int high, int max_depth, Vec<T> &data)
287{
288 it_assert((low >= 0) && (high > low) && (high < data.size()),
289 "Sort::sort(): low or high out of bounds");
290 IntroSort(low, high, max_depth, data._data());
291}
292
293// INTRO SORT INDEX
294template<class T>
295ivec Sort<T>::intro_sort_index(int low, int high, int max_depth,
296 const Vec<T> &data)
297{
298 int N = data.size();
299 it_assert((low >= 0) && (high > low) && (high < N),
300 "Sort::sort(): low or high out of bounds");
301
302 ivec indexlist(N);
303 for (int i = 0; i < N; ++i) {
304 indexlist(i) = i;
305 }
306
307 IntroSort_Index(low, high, max_depth, indexlist._data(), data._data());
308
309 return indexlist;
310}
311
312
313// ----------------------------------------------------------------------
314// Private functions for sorting methods
315// ----------------------------------------------------------------------
316
317template<class T>
318void Sort<T>::IntroSort(int low, int high, int max_depth, T data[])
319{
320 if (high - low > 16) {
321 max_depth--;
322 if (max_depth == 0) {
323 HeapSort(low, high, data);
324 return;
325 }
326
327 if (high > low) {
328 T a = data[low];
329 int plow = low;
330 int phigh = high;
331 T test = data[phigh];
332 while (plow < phigh) {
333 if (test < a) {
334 data[plow] = test;
335 plow++;
336 test = data[plow];
337 }
338 else {
339 data[phigh] = test;
340 phigh--;
341 test = data[phigh];
342 }
343 }
344 data[plow] = a;
345 IntroSort(low, plow - 1, max_depth, data);
346 IntroSort(plow + 1, high, max_depth, data);
347 return;
348 }
349 }
350 else {
351 InsertSort(low, high, data);
352 return;
353 }
354}
355
356template<class T>
357void Sort<T>::IntroSort_Index(int low, int high, int max_depth,
358 int indexlist[], const T data[])
359{
360 if (high - low > 16) {
361 max_depth--;
362 if (max_depth == 0) {
363 HeapSort_Index(low, high, indexlist, data);
364 return;
365 }
366
367 if (high > low) {
368 int aindex = indexlist[low];
369 T a = data[aindex];
370 int plow = low;
371 int phigh = high;
372 int testindex = indexlist[phigh];
373 T test = data[testindex];
374 while (plow < phigh) {
375 if (test < a) {
376 indexlist[plow] = testindex;
377 plow++;
378 testindex = indexlist[plow];
379 test = data[testindex];
380 }
381 else {
382 indexlist[phigh] = testindex;
383 phigh--;
384 testindex = indexlist[phigh];
385 test = data[testindex];
386 }
387 }
388 indexlist[plow] = aindex;
389 IntroSort_Index(low, plow - 1, max_depth, indexlist, data);
390 IntroSort_Index(plow + 1, high, max_depth, indexlist, data);
391 }
392 }
393 else {
394 InsertSort_Index(low, high, indexlist, data);
395 return;
396 }
397}
398
399template <class T>
400void Sort<T>::QuickSort(int low, int high, T data[])
401{
402 if (high > low) {
403 T a = data[low];
404 int plow = low;
405 int phigh = high;
406 T test = data[phigh];
407 while (plow < phigh) {
408 if (test < a) {
409 data[plow] = test;
410 plow++;
411 test = data[plow];
412 }
413 else {
414 data[phigh] = test;
415 phigh--;
416 test = data[phigh];
417 }
418 }
419 data[plow] = a;
420 QuickSort(low, plow - 1, data);
421 QuickSort(plow + 1, high, data);
422 }
423}
424
425template<class T>
426void Sort<T>::QuickSort_Index(int low, int high, int indexlist[],
427 const T data[])
428{
429 if (high > low) {
430 int aindex = indexlist[low];
431 T a = data[aindex];
432 int plow = low;
433 int phigh = high;
434 int testindex = indexlist[phigh];
435 T test = data[testindex];
436 while (plow < phigh) {
437 if (test < a) {
438 indexlist[plow] = testindex;
439 plow++;
440 testindex = indexlist[plow];
441 test = data[testindex];
442 }
443 else {
444 indexlist[phigh] = testindex;
445 phigh--;
446 testindex = indexlist[phigh];
447 test = data[testindex];
448 }
449 }
450 indexlist[plow] = aindex;
451 QuickSort_Index(low, plow - 1, indexlist, data);
452 QuickSort_Index(plow + 1, high, indexlist, data);
453 }
454}
455
456template<class T>
457void Sort<T>::HeapSort(int low, int high, T data[])
458{
459 int size = (high + 1) - low;
460 int i = size / 2;
461 T temp;
462 while (1) {
463 if (i > 0)
464 temp = data[--i + low];
465 else {
466 if (size-- == 0)
467 break;
468 temp = data[size + low];
469 data[size + low] = data[low];
470 }
471
472 int parent = i;
473 int child = i * 2 + 1;
474
475 while (child < size) {
476 if (child + 1 < size && data[child + 1 + low] > data[child + low])
477 child++;
478 if (data[child + low] > temp) {
479 data[parent + low] = data[child + low];
480 parent = child;
481 child = parent * 2 + 1;
482 }
483 else
484 break;
485 }
486 data[parent + low] = temp;
487 }
488}
489
490template<class T>
491void Sort<T>::HeapSort_Index(int low, int high, int indexlist[],
492 const T data[])
493{
494 int size = (high + 1) - low;
495 int i = size / 2;
496
497 while (1) {
498 T tempValue;
499 int tempIndex;
500 if (i > 0) {
501 i--;
502 tempValue = data[indexlist[i + low]];
503 tempIndex = indexlist[i + low];
504 }
505 else {
506 if (size-- == 0)
507 break;
508 tempValue = data[indexlist[size + low]];
509 tempIndex = indexlist[size + low];
510 indexlist[size+low] = indexlist[low];
511 }
512
513 int parent = i;
514 int child = i * 2 + 1;
515
516 while (child < size) {
517 if ((child + 1 < size)
518 && data[indexlist[child + 1 + low]] > data[indexlist[child + low]])
519 child++;
520 if (data[indexlist[child + low]] > tempValue) {
521 indexlist[parent + low] = indexlist[child + low];
522 parent = child;
523 child = parent * 2 + 1;
524 }
525 else
526 break;
527 }
528 indexlist[parent + low] = tempIndex;
529 }
530}
531
532template<class T>
533void Sort<T>::InsertSort(int low, int high, T data[])
534{
535 for (int i = low + 1; i <= high; i++) {
536 T value = data[i];
537 int j;
538 for (j = i - 1; j >= low && data[j] > value; j--) {
539 data[j + 1] = data[j];
540 }
541 data[j + 1] = value;
542 }
543}
544
545template<class T>
546void Sort<T>::InsertSort_Index(int low, int high, int indexlist[],
547 const T data[])
548{
549 for (int i = low + 1; i <= high; i++) {
550 T value = data[indexlist[i]];
551 int tempIndex = indexlist[i];
552 int j;
553 for (j = i - 1; j >= low && data[indexlist[j]] > value; j--) {
554 indexlist[j + 1] = indexlist[j];
555 }
556 indexlist[j + 1] = tempIndex;
557 }
558}
559
560
561} // namespace itpp
562
563#endif // #ifndef SORT_H
Class for sorting of vectors.
Definition: sort.h:100
void sort(int low, int high, Vec< T > &data)
Sorting function of a subset of a vector data.
Definition: sort.h:215
void set_method(SORTING_METHOD method)
Set sorting method.
Definition: sort.h:106
SORTING_METHOD get_method() const
Get current sorting method.
Definition: sort.h:109
void intro_sort(int low, int high, int max_depth, Vec< T > &data)
Introsort function of a subset of a vector data.
Definition: sort.h:286
ivec sort_index(int low, int high, const Vec< T > &data)
Sorting function that returns a sorted index vector.
Definition: sort.h:245
ivec intro_sort_index(int low, int high, int max_depth, const Vec< T > &data)
Introsort function, which returns a sorted index vector.
Definition: sort.h:295
Sort(SORTING_METHOD method=INTROSORT)
Constructor that sets Intro Sort method by default.
Definition: sort.h:103
Vector Class (Templated)
Definition: vec.h:245
ivec sort_index(const Vec< T > &data, SORTING_METHOD method=INTROSORT)
Return an index vector corresponding to a sorted vector data in increasing order.
Definition: sort.h:203
Num_T * _data()
Get the pointer to the internal structure. Not recommended for use.
Definition: vec.h:492
int size() const
The size of the vector.
Definition: vec.h:271
void sort(Vec< T > &data, SORTING_METHOD method=INTROSORT)
Sort the data vector in increasing order.
Definition: sort.h:187
Definitions of converters between different vector and matrix types.
#define it_error(s)
Abort unconditionally.
Definition: itassert.h:126
#define it_assert(t, s)
Abort if t is not true.
Definition: itassert.h:94
int levels2bits(int n)
Calculate the number of bits needed to represent n different values (levels).
Definition: log_exp.h:92
int size(const Vec< T > &v)
Length of vector.
Definition: matfunc.h:55
Logarithmic and exponenential functions - header file.
itpp namespace
Definition: itmex.h:37
SORTING_METHOD
Sorting algorithms that can be used in a Sort class.
Definition: sort.h:48
Templated Vector Class Definitions.
SourceForge Logo

Generated on Tue Jan 24 2023 00:00:00 for IT++ by Doxygen 1.9.5