1 /* ------------------------------------------------------------------ 2 * Copyright (C) 1998-2009 PacketVideo 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 13 * express or implied. 14 * See the License for the specific language governing permissions 15 * and limitations under the License. 16 * ------------------------------------------------------------------- 17 */ 18 /* 19 20 Filename: shellsort.c 21 22 ------------------------------------------------------------------------------ 23 REVISION HISTORY 24 25 26 Who: Date: MM/DD/YYYY 27 Description: 28 29 ------------------------------------------------------------------------------ 30 INPUT AND OUTPUT DEFINITIONS 31 32 33 34 ------------------------------------------------------------------------------ 35 FUNCTION DESCRIPTION 36 37 Sorting routine 38 ------------------------------------------------------------------------------ 39 REQUIREMENTS 40 41 42 ------------------------------------------------------------------------------ 43 REFERENCES 44 45 46 47 ------------------------------------------------------------------------------ 48 PSEUDO-CODE 49 50 ------------------------------------------------------------------------------ 51 */ 52 53 54 /*---------------------------------------------------------------------------- 55 ; INCLUDES 56 ----------------------------------------------------------------------------*/ 57 58 #ifdef AAC_PLUS 59 60 61 #include "shellsort.h" 62 63 /*---------------------------------------------------------------------------- 64 ; MACROS 65 ; Define module specific macros here 66 ----------------------------------------------------------------------------*/ 67 68 69 /*---------------------------------------------------------------------------- 70 ; DEFINES 71 ; Include all pre-processor statements here. Include conditional 72 ; compile variables also. 73 ----------------------------------------------------------------------------*/ 74 75 /*---------------------------------------------------------------------------- 76 ; LOCAL FUNCTION DEFINITIONS 77 ; Function Prototype declaration 78 ----------------------------------------------------------------------------*/ 79 80 /*---------------------------------------------------------------------------- 81 ; LOCAL STORE/BUFFER/POINTER DEFINITIONS 82 ; Variable declaration - defined here and used outside this module 83 ----------------------------------------------------------------------------*/ 84 85 /*---------------------------------------------------------------------------- 86 ; EXTERNAL FUNCTION REFERENCES 87 ; Declare functions defined elsewhere and referenced in this module 88 ----------------------------------------------------------------------------*/ 89 90 /*---------------------------------------------------------------------------- 91 ; EXTERNAL GLOBAL STORE/BUFFER/POINTER REFERENCES 92 ; Declare variables used in this module but defined elsewhere 93 ----------------------------------------------------------------------------*/ 94 95 /*---------------------------------------------------------------------------- 96 ; FUNCTION CODE 97 ----------------------------------------------------------------------------*/ 98 99 100 void shellsort(Int32 in[], Int32 n) 101 { 102 103 Int32 i; 104 Int32 j; 105 Int32 v; 106 Int32 inc = 1; 107 108 do 109 { 110 inc = 3 * inc + 1; 111 } 112 while (inc <= n); 113 114 do 115 { 116 inc = inc / 3; 117 for (i = inc + 1; i <= n; i++) 118 { 119 v = in[i-1]; 120 j = i; 121 while (in[j-inc-1] > v) 122 { 123 in[j-1] = in[j-inc-1]; 124 j -= inc; 125 if (j <= inc) 126 { 127 break; 128 } 129 } 130 in[j-1] = v; 131 } 132 } 133 while (inc > 1); 134 135 } 136 137 #endif 138 139
