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