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  
 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  
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  
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   */