1 /* ----------------------------------------------------------------------
2 * Project: CMSIS DSP Library
3 * Title: arm_quick_sort_f32.c
4 * Description: Floating point quick sort
5 *
6 * $Date: 23 April 2021
7 * $Revision: V1.9.0
8 *
9 * Target Processor: Cortex-M and Cortex-A cores
10 * -------------------------------------------------------------------- */
11 /*
12 * Copyright (C) 2010-2021 ARM Limited or its affiliates. All rights reserved.
13 *
14 * SPDX-License-Identifier: Apache-2.0
15 *
16 * Licensed under the Apache License, Version 2.0 (the License); you may
17 * not use this file except in compliance with the License.
18 * You may obtain a copy of the License at
19 *
20 * www.apache.org/licenses/LICENSE-2.0
21 *
22 * Unless required by applicable law or agreed to in writing, software
23 * distributed under the License is distributed on an AS IS BASIS, WITHOUT
24 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
25 * See the License for the specific language governing permissions and
26 * limitations under the License.
27 */
28
29 #include "arm_sorting.h"
30
arm_quick_sort_partition_f32(float32_t * pSrc,int32_t first,int32_t last,uint8_t dir)31 static uint32_t arm_quick_sort_partition_f32(float32_t *pSrc, int32_t first, int32_t last, uint8_t dir)
32 {
33 /* This function will be called */
34 int32_t i, j, pivot_index;
35 float32_t pivot;
36 float32_t temp;
37
38 /* The first element is the pivot */
39 pivot_index = first;
40 pivot = pSrc[pivot_index];
41
42 /* Initialize indices for do-while loops */
43 i = first - 1;
44 j = last + 1;
45
46 while(i < j)
47 {
48 /* The loop will stop as soon as the indices i and j cross each other.
49 *
50 * This event will happen surely since the values of the indices are incremented and
51 * decrement in the do-while loops that are executed at least once.
52 * It is impossible to loop forever inside the do-while loops since the pivot is
53 * always an element of the array and the conditions cannot be always true (at least
54 * the i-th or the j-th element will be equal to the pivot-th element).
55 * For example, in the extreme case of an ordered array the do-while loop related to i will stop
56 * at the first iteration (because pSrc[i]=pSrc[pivot] already), and the loop related to j
57 * will stop after (last-first) iterations (when j=pivot=i=first). j is returned and
58 * j+1 is going to be used as pivot by other calls of the function, until j=pivot=last. */
59
60 /* Move indices to the right and to the left */
61 if(dir)
62 {
63 /* Compare left elements with pivot */
64 do
65 {
66 i++;
67 } while (pSrc[i] < pivot && i<last);
68
69 /* Compare right elements with pivot */
70 do
71 {
72 j--;
73 } while (pSrc[j] > pivot);
74 }
75 else
76 {
77 /* Compare left elements with pivot */
78 do
79 {
80 i++;
81 } while (pSrc[i] > pivot && i<last);
82
83 /* Compare right elements with pivot */
84 do
85 {
86 j--;
87 } while (pSrc[j] < pivot);
88 }
89
90 /* If the indices didn't cross each other */
91 if (i < j)
92 {
93 /* i and j are in the wrong position -> Swap */
94 temp=pSrc[i];
95 pSrc[i]=pSrc[j];
96 pSrc[j]=temp;
97 }
98 }
99
100 return j;
101 }
102
arm_quick_sort_core_f32(float32_t * pSrc,int32_t first,int32_t last,uint8_t dir)103 static void arm_quick_sort_core_f32(float32_t *pSrc, int32_t first, int32_t last, uint8_t dir)
104 {
105 /* If the array [first ... last] has more than one element */
106 if(first<last)
107 {
108 int32_t pivot;
109
110 /* Compute pivot */
111 pivot = arm_quick_sort_partition_f32(pSrc, first, last, dir);
112
113 /* Iterate algorithm with two sub-arrays [first ... pivot] and [pivot+1 ... last] */
114 arm_quick_sort_core_f32(pSrc, first, pivot, dir);
115 arm_quick_sort_core_f32(pSrc, pivot+1, last, dir);
116 }
117 }
118
119 /**
120 @ingroup groupSupport
121 */
122
123 /**
124 @addtogroup Sorting
125 @{
126 */
127
128 /**
129 * @private
130 * @param[in] S points to an instance of the sorting structure.
131 * @param[in,out] pSrc points to the block of input data.
132 * @param[out] pDst points to the block of output data.
133 * @param[in] blockSize number of samples to process.
134 *
135 * @par Algorithm
136 * The quick sort algorithm is a comparison algorithm that
137 * divides the input array into two smaller sub-arrays and
138 * recursively sort them. An element of the array (the pivot)
139 * is chosen, all the elements with values smaller than the
140 * pivot are moved before the pivot, while all elements with
141 * values greater than the pivot are moved after it (partition).
142 *
143 * @par
144 * In this implementation the Hoare partition scheme has been
145 * used [Hoare, C. A. R. (1 January 1962). "Quicksort". The Computer
146 * Journal. 5 (1): 10...16.] The first element has always been chosen
147 * as the pivot. The partition algorithm guarantees that the returned
148 * pivot is never placed outside the vector, since it is returned only
149 * when the pointers crossed each other. In this way it isn't
150 * possible to obtain empty partitions and infinite recursion is avoided.
151 *
152 * @par
153 * It's an in-place algorithm. In order to obtain an out-of-place
154 * function, a memcpy of the source vector is performed.
155 */
156
arm_quick_sort_f32(const arm_sort_instance_f32 * S,float32_t * pSrc,float32_t * pDst,uint32_t blockSize)157 void arm_quick_sort_f32(
158 const arm_sort_instance_f32 * S,
159 float32_t * pSrc,
160 float32_t * pDst,
161 uint32_t blockSize)
162 {
163 float32_t * pA;
164
165 /* Out-of-place */
166 if(pSrc != pDst)
167 {
168 memcpy(pDst, pSrc, blockSize*sizeof(float32_t) );
169 pA = pDst;
170 }
171 else
172 pA = pSrc;
173
174 arm_quick_sort_core_f32(pA, 0, blockSize-1, S->dir);
175 /* The previous function could be called recursively a maximum
176 * of (blockSize-1) times, generating a stack consumption of 4*(blockSize-1) bytes. */
177 }
178
179 /**
180 @} end of Sorting group
181 */
182
