1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2004-2008 Jean Privat <jean@pryen.org>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
18 fun quicksort
(a
: Array[Comparable])
20 sub_quicksort
(a
, 0, a
.length-1
)
23 fun sub_quicksort
(a
: Array[Comparable], g
: Int, d
: Int)
35 while j
>= g
and a
[j
] >= pivot
do
46 sub_quicksort
(a
, g
, i-1
)
47 sub_quicksort
(a
, i
+1, d
)
50 fun heapsort
(a
: Array[Comparable])
52 var i
= a
.length
/ 2 - 1
54 sift_down
(a
, i
, a
.length
- 1)
68 fun sift_down
(a
: Array[Comparable], root
: Int, bottom
: Int)
72 var maxchild
= root
* 2 + 1
73 if maxchild
> bottom
then
75 else if maxchild
< bottom
and a
[maxchild
] < a
[root
* 2 + 2] then
76 maxchild
= root
* 2 + 2
91 var q
= [6, 7, 3, 9, 1, 4, 2, 8, 5]
92 var h
= [6, 7, 3, 9, 1, 4, 2, 8, 5]