diff options
author | Jean-Marc Valin <jmvalin@jmvalin.ca> | 2011-09-16 01:16:53 -0700 |
---|---|---|
committer | Jean-Marc Valin <jmvalin@jmvalin.ca> | 2011-09-16 01:16:53 -0700 |
commit | 1c2f5633d101c08b5ef8095a8682d3d52cbd952d (patch) | |
tree | 66f80e67f075db5fa5233759a89f475d8bedade2 /silk/sort.c | |
parent | fb3a437c9dabb4aafe4a3927158161590ed745ab (diff) | |
download | opus-1c2f5633d101c08b5ef8095a8682d3d52cbd952d.tar.gz |
Removed all the silk_ prefixes in source file names (not symbols)
Diffstat (limited to 'silk/sort.c')
-rw-r--r-- | silk/sort.c | 151 |
1 files changed, 151 insertions, 0 deletions
diff --git a/silk/sort.c b/silk/sort.c new file mode 100644 index 00000000..26d81715 --- /dev/null +++ b/silk/sort.c @@ -0,0 +1,151 @@ +/*********************************************************************** +Copyright (c) 2006-2011, Skype Limited. All rights reserved. +Redistribution and use in source and binary forms, with or without +modification, (subject to the limitations in the disclaimer below) +are permitted provided that the following conditions are met: +- Redistributions of source code must retain the above copyright notice, +this list of conditions and the following disclaimer. +- Redistributions in binary form must reproduce the above copyright +notice, this list of conditions and the following disclaimer in the +documentation and/or other materials provided with the distribution. +- Neither the name of Skype Limited, nor the names of specific +contributors, may be used to endorse or promote products derived from +this software without specific prior written permission. +NO EXPRESS OR IMPLIED LICENSES TO ANY PARTY'S PATENT RIGHTS ARE GRANTED +BY THIS LICENSE. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND +CONTRIBUTORS ''AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, +BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND +FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE +COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, +INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF +USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON +ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +***********************************************************************/ + +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif + +/* Insertion sort (fast for already almost sorted arrays): */ +/* Best case: O(n) for an already sorted array */ +/* Worst case: O(n^2) for an inversely sorted array */ +/* */ +/* Shell short: http://en.wikipedia.org/wiki/Shell_sort */ + +#include "SigProc_FIX.h" + +void silk_insertion_sort_increasing( + opus_int32 *a, /* I/O: Unsorted / Sorted vector */ + opus_int *idx, /* O: Index vector for the sorted elements */ + const opus_int L, /* I: Vector length */ + const opus_int K /* I: Number of correctly sorted positions */ +) +{ + opus_int32 value; + opus_int i, j; + + /* Safety checks */ + silk_assert( K > 0 ); + silk_assert( L > 0 ); + silk_assert( L >= K ); + + /* Write start indices in index vector */ + for( i = 0; i < K; i++ ) { + idx[ i ] = i; + } + + /* Sort vector elements by value, increasing order */ + for( i = 1; i < K; i++ ) { + value = a[ i ]; + for( j = i - 1; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { + a[ j + 1 ] = a[ j ]; /* Shift value */ + idx[ j + 1 ] = idx[ j ]; /* Shift index */ + } + a[ j + 1 ] = value; /* Write value */ + idx[ j + 1 ] = i; /* Write index */ + } + + /* If less than L values are asked for, check the remaining values, */ + /* but only spend CPU to ensure that the K first values are correct */ + for( i = K; i < L; i++ ) { + value = a[ i ]; + if( value < a[ K - 1 ] ) { + for( j = K - 2; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { + a[ j + 1 ] = a[ j ]; /* Shift value */ + idx[ j + 1 ] = idx[ j ]; /* Shift index */ + } + a[ j + 1 ] = value; /* Write value */ + idx[ j + 1 ] = i; /* Write index */ + } + } +} + +void silk_insertion_sort_decreasing_int16( + opus_int16 *a, /* I/O: Unsorted / Sorted vector */ + opus_int *idx, /* O: Index vector for the sorted elements */ + const opus_int L, /* I: Vector length */ + const opus_int K /* I: Number of correctly sorted positions */ +) +{ + opus_int i, j; + opus_int value; + + /* Safety checks */ + silk_assert( K > 0 ); + silk_assert( L > 0 ); + silk_assert( L >= K ); + + /* Write start indices in index vector */ + for( i = 0; i < K; i++ ) { + idx[ i ] = i; + } + + /* Sort vector elements by value, decreasing order */ + for( i = 1; i < K; i++ ) { + value = a[ i ]; + for( j = i - 1; ( j >= 0 ) && ( value > a[ j ] ); j-- ) { + a[ j + 1 ] = a[ j ]; /* Shift value */ + idx[ j + 1 ] = idx[ j ]; /* Shift index */ + } + a[ j + 1 ] = value; /* Write value */ + idx[ j + 1 ] = i; /* Write index */ + } + + /* If less than L values are asked for, check the remaining values, */ + /* but only spend CPU to ensure that the K first values are correct */ + for( i = K; i < L; i++ ) { + value = a[ i ]; + if( value > a[ K - 1 ] ) { + for( j = K - 2; ( j >= 0 ) && ( value > a[ j ] ); j-- ) { + a[ j + 1 ] = a[ j ]; /* Shift value */ + idx[ j + 1 ] = idx[ j ]; /* Shift index */ + } + a[ j + 1 ] = value; /* Write value */ + idx[ j + 1 ] = i; /* Write index */ + } + } +} + +void silk_insertion_sort_increasing_all_values_int16( + opus_int16 *a, /* I/O: Unsorted / Sorted vector */ + const opus_int L /* I: Vector length */ +) +{ + opus_int value; + opus_int i, j; + + /* Safety checks */ + silk_assert( L > 0 ); + + /* Sort vector elements by value, increasing order */ + for( i = 1; i < L; i++ ) { + value = a[ i ]; + for( j = i - 1; ( j >= 0 ) && ( value < a[ j ] ); j-- ) { + a[ j + 1 ] = a[ j ]; /* Shift value */ + } + a[ j + 1 ] = value; /* Write value */ + } +} |