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 100void 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