JKQTPlotter trunk/v5.0.0
an extensive Qt5+Qt6 Plotter framework (including a feature-richt plotter widget, a speed-optimized, but limited variant and a LaTeX equation renderer!), written fully in C/C++ and without external dependencies
Loading...
Searching...
No Matches
jkqtpalgorithms.h
1/*
2 Copyright (c) 2008-2024 Jan W. Krieger (<jan@jkrieger.de>)
3
4
5
6 This software is free software: you can redistribute it and/or modify
7 it under the terms of the GNU Lesser General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU Lesser General Public License for more details.
15
16 You should have received a copy of the GNU Lesser General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
18*/
19
20
21
22#ifndef JKQTPALGORITHMS_H_INCLUDED
23#define JKQTPALGORITHMS_H_INCLUDED
24#include "jkqtmath/jkqtmath_imexport.h"
25
26
27
28
29/*! \brief swap two elements \a l and \a r in an array \a a
30 \ingroup jkqtptools_algorithms
31
32*/
33template <class T>
34inline void jkqtpSwap(T* a, int l, int r){
35 const T tmp=a[l];
36 a[l]=a[r];
37 a[r]=tmp;
38}
39
40
41
42/*! \brief QuickSort (recursive implementation)
43 \ingroup jkqtptools_algorithms
44 \internal
45
46 implementation from http://www.linux-related.de/index.html?/coding/sort/sort_quick.htm
47*/
48template <class T>
49inline void jkqtpQuicksort(T* a, int l, int r){
50 if(r>l){
51 int i=l-1;
52 int j=r;
53
54 for(;;){
55 while(a[++i]<a[r]);
56 while(a[--j]>a[r] && j>i);
57 if(i>=j) break;
58 jkqtpSwap<T>(a, i, j);
59 }
60 jkqtpSwap<T>(a, i, r);
61
62 jkqtpQuicksort(a, l, i-1);
63 jkqtpQuicksort(a, i+1, r);
64 }
65}
66
67/*! \brief QuickSort (recursive implementation), sorts \a a2 alongside \a a, using \a a as sort criterion
68 \ingroup jkqtptools_algorithms
69 \internal
70
71 implementation from http://www.linux-related.de/index.html?/coding/sort/sort_quick.htm
72*/
73template <class T, class T2>
74inline void jkqtpQuicksortDual(T* a, T2* a2, int l, int r){
75 if(r>l){
76 int i=l-1;
77 int j=r;
78
79 for(;;){
80 while(a[++i]<a[r]);
81 while(a[--j]>a[r] && j>i);
82 if(i>=j) break;
83 jkqtpSwap(a, i, j);
84 jkqtpSwap(a2, i, j);
85 }
86 jkqtpSwap(a, i, r);
87 jkqtpSwap(a2, i, r);
88
89 jkqtpQuicksortDual(a, a2, l, i-1);
90 jkqtpQuicksortDual(a, a2, i+1, r);
91 }
92}
93
94
95
96/*! \brief sort the given array and return the result in \a output (implies a copy!!!)
97 \ingroup jkqtptools_algorithms
98
99 \param input array to be sorted
100 \param N size of the array input
101 \param output if \c !=nullptr data is written here (the memory location pointed at by \a output has to have at least the length \a N !!!),
102 otherwise the array input is sorted inplace.
103
104 */
105template <class T>
106inline void jkqtpQuicksort(const T* input, long long N, T* output) {
107 if ((!input)) return ;
108 if (N<=0) return;
109 T* data=output;
110 memcpy(output, input, N*sizeof(T));
111 jkqtpQuicksort(data, 0, N-1);
112}
113
114
115
116
117/*! \brief sort the given arrays, using \a input as sort criterion
118 \ingroup jkqtptools_algorithms
119
120 \param input array to be sorted (the sort criterion)
121 \param input2 array to be sorted (sorted alongside \a input )
122 \param N size of the array input
123
124 */
125template <class T, class T2>
126inline void jkqtpQuicksortDual(T* input, T2* input2, int N) {
127 if ((!input)) return ;
128 if (N<=0) return;
129 jkqtpQuicksortDual(input, input2, 0, N-1);
130}
131
132/*! \brief sort the given arrays, using \a input as sort criterion, returns the results in \a output and \a output2 (implied copies of the data!)
133 \ingroup jkqtptools_algorithms
134
135 \param input array to be sorted (the sort criterion)
136 \param input2 array to be sorted (sorted alongside \a input )
137 \param N size of the array input
138 \param output result is written here (the memory location pointed at by \a output has to have at least the length \a N !!!),
139 otherwise the array input is sorted inplace.
140 \param output2 result is written here (the memory location pointed at by \a output has to have at least the length \a N !!!),
141 otherwise the array input is sorted inplace.
142
143 */
144template <class T, class T2>
145inline void jkqtpQuicksortDual(const T* input, const T2* input2, int N, T* output, T2* output2) {
146 if ((!input)) return ;
147 if (N<=0) return;
148 T* data=output;
149 memcpy(output, input, N*sizeof(T));
150 T2* data2=output2;
151 memcpy(output2, input2, N*sizeof(T2));
152 jkqtpQuicksortDual(data, data2, 0, N-1);
153}
154
155
156#endif // JKQTPALGORITHMS_H_INCLUDED
void jkqtpQuicksortDual(T *a, T2 *a2, int l, int r)
QuickSort (recursive implementation), sorts a2 alongside a, using a as sort criterion.
Definition jkqtpalgorithms.h:74
void jkqtpSwap(T *a, int l, int r)
swap two elements l and r in an array a
Definition jkqtpalgorithms.h:34
void jkqtpQuicksort(T *a, int l, int r)
QuickSort (recursive implementation)
Definition jkqtpalgorithms.h:49