Line data    Source code

       1             : /***********************************************************************
       2             : Copyright (c) 2006-2011, Skype Limited. All rights reserved.
       3             : Redistribution and use in source and binary forms, with or without
       4             : modification, are permitted provided that the following conditions
       5             : are met:
       6             : - Redistributions of source code must retain the above copyright notice,
       7             : this list of conditions and the following disclaimer.
       8             : - Redistributions in binary form must reproduce the above copyright
       9             : notice, this list of conditions and the following disclaimer in the
      10             : documentation and/or other materials provided with the distribution.
      11             : - Neither the name of Internet Society, IETF or IETF Trust, nor the
      12             : names of specific contributors, may be used to endorse or promote
      13             : products derived from this software without specific prior written
      14             : permission.
      15             : THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
      16             : AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
      17             : IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
      18             : ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
      19             : LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
      20             : CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
      21             : SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
      22             : INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
      23             : CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
      24             : ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
      25             : POSSIBILITY OF SUCH DAMAGE.
      26             : ***********************************************************************/
      27             : 
      28             : #ifdef HAVE_CONFIG_H
      29             : #include "config.h"
      30             : #endif
      31             : 
      32             : /* Insertion sort (fast for already almost sorted arrays):  */
      33             : /* Best case:  O(n)   for an already sorted array           */
      34             : /* Worst case: O(n^2) for an inversely sorted array         */
      35             : 
      36             : #include "typedef.h"
      37             : #include "SigProc_FLP.h"
      38             : 
      39           0 : void silk_insertion_sort_decreasing_FLP(
      40             :     silk_float          *a,                 /* I/O  Unsorted / Sorted vector                                    */
      41             :     opus_int            *idx,               /* O    Index vector for the sorted elements                        */
      42             :     const opus_int      L,                  /* I    Vector length                                               */
      43             :     const opus_int      K                   /* I    Number of correctly sorted positions                        */
      44             : )
      45             : {
      46             :     silk_float value;
      47             :     opus_int   i, j;
      48             : 
      49             :     /* Safety checks */
      50           0 :     silk_assert( K >  0 );
      51           0 :     silk_assert( L >  0 );
      52           0 :     silk_assert( L >= K );
      53             : 
      54             :     /* Write start indices in index vector */
      55           0 :     for( i = 0; i < K; i++ ) {
      56           0 :         idx[ i ] = i;
      57             :     }
      58             : 
      59             :     /* Sort vector elements by value, decreasing order */
      60           0 :     for( i = 1; i < K; i++ ) {
      61           0 :         value = a[ i ];
      62           0 :         for( j = i - 1; ( j >= 0 ) && ( value > a[ j ] ); j-- ) {
      63           0 :             a[ j + 1 ]   = a[ j ];      /* Shift value */
      64           0 :             idx[ j + 1 ] = idx[ j ];    /* Shift index */
      65             :         }
      66           0 :         a[ j + 1 ]   = value;   /* Write value */
      67           0 :         idx[ j + 1 ] = i;       /* Write index */
      68             :     }
      69             : 
      70             :     /* If less than L values are asked check the remaining values,      */
      71             :     /* but only spend CPU to ensure that the K first values are correct */
      72           0 :     for( i = K; i < L; i++ ) {
      73           0 :         value = a[ i ];
      74           0 :         if( value > a[ K - 1 ] ) {
      75           0 :             for( j = K - 2; ( j >= 0 ) && ( value > a[ j ] ); j-- ) {
      76           0 :                 a[ j + 1 ]   = a[ j ];      /* Shift value */
      77           0 :                 idx[ j + 1 ] = idx[ j ];    /* Shift index */
      78             :             }
      79           0 :             a[ j + 1 ]   = value;   /* Write value */
      80           0 :             idx[ j + 1 ] = i;       /* Write index */
      81             :         }
      82             :     }
      83           0 : }