1 /* ----------------------------------------------------------------------
2 * Project: CMSIS DSP Library
3 * Title: arm_heap_sort_f32.c
4 * Description: Floating point heap 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 "dsp/support_functions.h"
30 #include "arm_sorting.h"
31
32
33
arm_heapify(float32_t * pSrc,uint32_t n,uint32_t i,uint8_t dir)34 static void arm_heapify(float32_t * pSrc, uint32_t n, uint32_t i, uint8_t dir)
35 {
36 /* Put all the elements of pSrc in heap order */
37 uint32_t k = i; // Initialize largest/smallest as root
38 uint32_t l = 2*i + 1; // left = 2*i + 1
39 uint32_t r = 2*i + 2; // right = 2*i + 2
40 float32_t temp;
41
42 if (l < n && dir==(pSrc[l] > pSrc[k]) )
43 k = l;
44
45 if (r < n && dir==(pSrc[r] > pSrc[k]) )
46 k = r;
47
48 if (k != i)
49 {
50 temp = pSrc[i];
51 pSrc[i]=pSrc[k];
52 pSrc[k]=temp;
53
54 arm_heapify(pSrc, n, k, dir);
55 }
56 }
57
58 /**
59 @ingroup groupSupport
60 */
61
62 /**
63 @addtogroup Sorting
64 @{
65 */
66
67 /**
68 * @private
69 * @param[in] S points to an instance of the sorting structure.
70 * @param[in] pSrc points to the block of input data.
71 * @param[out] pDst points to the block of output data
72 * @param[in] blockSize number of samples to process.
73 *
74 * @par Algorithm
75 * The heap sort algorithm is a comparison algorithm that
76 * divides the input array into a sorted and an unsorted region,
77 * and shrinks the unsorted region by extracting the largest
78 * element and moving it to the sorted region. A heap data
79 * structure is used to find the maximum.
80 *
81 * @par It's an in-place algorithm. In order to obtain an out-of-place
82 * function, a memcpy of the source vector is performed.
83 */
arm_heap_sort_f32(const arm_sort_instance_f32 * S,float32_t * pSrc,float32_t * pDst,uint32_t blockSize)84 void arm_heap_sort_f32(
85 const arm_sort_instance_f32 * S,
86 float32_t * pSrc,
87 float32_t * pDst,
88 uint32_t blockSize)
89 {
90 float32_t * pA;
91 int32_t i;
92 float32_t temp;
93
94 if(pSrc != pDst) // out-of-place
95 {
96 memcpy(pDst, pSrc, blockSize*sizeof(float32_t) );
97 pA = pDst;
98 }
99 else
100 pA = pSrc;
101
102 // Build the heap array so that the largest value is the root
103 for (i = blockSize/2 - 1; i >= 0; i--)
104 arm_heapify(pA, blockSize, i, S->dir);
105
106 for (i = blockSize - 1; i >= 0; i--)
107 {
108 // Swap
109 temp = pA[i];
110 pA[i] = pA[0];
111 pA[0] = temp;
112
113 // Restore heap order
114 arm_heapify(pA, i, 0, S->dir);
115 }
116 }
117 /**
118 @} end of Sorting group
119 */
120
