Quicksort.cpp
Go to the documentation of this file.
1 // ****************************************************************************
2 // This file is part of the Integrating Vision Toolkit (IVT).
3 //
4 // The IVT is maintained by the Karlsruhe Institute of Technology (KIT)
5 // (www.kit.edu) in cooperation with the company Keyetech (www.keyetech.de).
6 //
7 // Copyright (C) 2014 Karlsruhe Institute of Technology (KIT).
8 // All rights reserved.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are met:
12 //
13 // 1. Redistributions of source code must retain the above copyright
14 // notice, this list of conditions and the following disclaimer.
15 //
16 // 2. Redistributions in binary form must reproduce the above copyright
17 // notice, this list of conditions and the following disclaimer in the
18 // documentation and/or other materials provided with the distribution.
19 //
20 // 3. Neither the name of the KIT nor the names of its contributors may be
21 // used to endorse or promote products derived from this software
22 // without specific prior written permission.
23 //
24 // THIS SOFTWARE IS PROVIDED BY THE KIT AND CONTRIBUTORS “AS IS” AND ANY
25 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
26 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
27 // DISCLAIMED. IN NO EVENT SHALL THE KIT OR CONTRIBUTORS BE LIABLE FOR ANY
28 // DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
29 // (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
31 // ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
32 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
33 // THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 // ****************************************************************************
35 // ****************************************************************************
36 // Filename: Quicksort.cpp
37 // Author: Kai Welke
38 // Date: 2005
39 // ****************************************************************************
40 
41 
42 // ****************************************************************************
43 // Includes
44 // ****************************************************************************
45 
46 #include <new> // for explicitly using correct new/delete operators on VC DSPs
47 
48 #include "Quicksort.h"
49 
50 
51 
52 // ****************************************************************************
53 // Functions
54 // ****************************************************************************
55 
56 // quicksort elements of float array by exchanging the elements
57 void Quicksort::Quicksort(float *pValues, int nLow, int nHigh)
58 {
59  int i = nLow;
60  int j = nHigh;
61 
62  const float fX = pValues[(nLow + nHigh) / 2];
63 
64  while (i <= j)
65  {
66  while (pValues[i] < fX) i++;
67  while (pValues[j] > fX) j--;
68 
69  if (i <= j)
70  {
71  float fTemp = pValues[i];
72  pValues[i] = pValues[j];
73  pValues[j] = fTemp;
74 
75  i++;
76  j--;
77  }
78  }
79 
80  if (nLow < j) Quicksort(pValues, nLow, j);
81  if (i < nHigh) Quicksort(pValues, i, nHigh);
82 }
83 
84 
85 // quicksort elements of float array in inverse order by exchanging the elements
86 void Quicksort::QuicksortInverse(float *pValues, int nLow, int nHigh)
87 {
88  int i = nLow;
89  int j = nHigh;
90 
91  const float fX = pValues[(nLow + nHigh) / 2];
92 
93  while (i <= j)
94  {
95  while (pValues[i] > fX) i++;
96  while (pValues[j] < fX) j--;
97 
98  if (i <= j)
99  {
100  float fTemp = pValues[i];
101  pValues[i] = pValues[j];
102  pValues[j] = fTemp;
103 
104  i++;
105  j--;
106  }
107  }
108 
109  if (nLow < j) QuicksortInverse(pValues, nLow, j);
110  if (i < nHigh) QuicksortInverse(pValues, i, nHigh);
111 }
112 
113 
114 void Quicksort::QuicksortWithMeta(float *pValues, void **ppMeta, int nLow, int nHigh)
115 {
116  int i = nLow;
117  int j = nHigh;
118 
119  const float fX = pValues[(nLow + nHigh) / 2];
120 
121  while (i <= j)
122  {
123  while (pValues[i] < fX) i++;
124  while (pValues[j] > fX) j--;
125 
126  if (i <= j)
127  {
128  const float fTemp = pValues[i];
129  pValues[i] = pValues[j];
130  pValues[j] = fTemp;
131 
132  void *pMetaTemp = ppMeta[i];
133  ppMeta[i] = ppMeta[j];
134  ppMeta[j] = pMetaTemp;
135 
136  i++;
137  j--;
138  }
139  }
140 
141  if (nLow < j) QuicksortWithMeta(pValues, ppMeta, nLow, j);
142  if (i < nHigh) QuicksortWithMeta(pValues, ppMeta, i, nHigh);
143 }
144 
145 void Quicksort::QuicksortInverseWithMeta(float *pValues, void **ppMeta, int nLow, int nHigh)
146 {
147  int i = nLow;
148  int j = nHigh;
149 
150  const float fX = pValues[(nLow + nHigh) / 2];
151 
152  while (i <= j)
153  {
154  while (pValues[i] > fX) i++;
155  while (pValues[j] < fX) j--;
156 
157  if (i <= j)
158  {
159  float fTemp = pValues[i];
160  pValues[i] = pValues[j];
161  pValues[j] = fTemp;
162 
163  void *pMetaTemp = ppMeta[i];
164  ppMeta[i] = ppMeta[j];
165  ppMeta[j] = pMetaTemp;
166 
167  i++;
168  j--;
169  }
170  }
171 
172  if (nLow < j) QuicksortInverseWithMeta(pValues, ppMeta, nLow, j);
173  if (i < nHigh) QuicksortInverseWithMeta(pValues, ppMeta, i, nHigh);
174 }
175 
176 
177 // quicksort vectors (float* in an array) due to the size of the size of the nSortByDimension'th element
178 // by exchanging the pointers
179 void Quicksort::QuicksortByElementOfVector(float **ppValues, int nLow, int nHigh, int nSortByDimension)
180 {
181  int i = nLow;
182  int j = nHigh;
183 
184  const float fX = ppValues[(nLow + nHigh) / 2][nSortByDimension];
185 
186  while ( i <= j )
187  {
188  while (ppValues[i][nSortByDimension] < fX) i++;
189  while (ppValues[j][nSortByDimension] > fX) j--;
190 
191  if (i <= j)
192  {
193  float *pfTemp = ppValues[i];
194  ppValues[i]=ppValues[j];
195  ppValues[j]=pfTemp;
196 
197  i++;
198  j--;
199  }
200  }
201 
202  if (nLow < j) QuicksortByElementOfVector(ppValues, nLow, j, nSortByDimension);
203  if (i < nHigh) QuicksortByElementOfVector(ppValues, i, nHigh, nSortByDimension);
204 }
static void QuicksortInverse(int *pOffsets, const int *pValues, int nLow, int nHigh)
void QuicksortByElementOfVector(float **ppValues, int nLow, int nHigh, int nSortByDimension)
Definition: Quicksort.cpp:179
void Quicksort(float *pValues, int nLow, int nHigh)
Definition: Quicksort.cpp:57
void QuicksortInverse(float *pValues, int nLow, int nHigh)
Definition: Quicksort.cpp:86
void QuicksortInverseWithMeta(float *pValues, void **ppMeta, int nLow, int nHigh)
Definition: Quicksort.cpp:145
void QuicksortWithMeta(float *pValues, void **ppMeta, int nLow, int nHigh)
Definition: Quicksort.cpp:114


asr_ivt
Author(s): Allgeyer Tobias, Hutmacher Robin, Kleinert Daniel, Meißner Pascal, Scholz Jonas, Stöckle Patrick
autogenerated on Mon Dec 2 2019 03:47:28