Sorting algorithms/Heapsort: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(→{{header|Pascal}}: replaced incorrect previous version) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (13 intermediate revisions by 6 users not shown) | |||
Line 2,220:
<syntaxhighlight lang="text">
n = len d[]
# make heap
for i = 2 to n
if d[i] > d[(i + 1) div 2]
j = i
repeat
h = (j + 1) div 2
until d[j] <= d[h]
swap d[j] d[h]
j = h
.
.
.
for i = n downto
swap d[1] d[i]
j = 1
ind = 2
while ind < i
if ind + 1 < i and d[ind + 1] > d[ind]
ind += 1
.
if d[j] < d[ind]
swap d[j] d[ind]
.
j = ind
ind = 2 * j
.
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
print data[]
</syntaxhighlight>
Line 2,918:
list
}</syntaxhighlight>
This is a better to read version. It includes comments and much better to understand and read function headers and loops.
It also has better readable variable names and can therefore be better used for study purposes.
It contains the same functions, even if a function with a single variable assignment in it is not very useful.
<syntaxhighlight lang="groovy">
def makeSwap (list, element1, element2) {
//exchanges two elements in a list.
//print a dot for each swap.
print "."
list[[element2,element1]] = list[[element1,element2]]
}
def checkSwap (list, child, parent) {
//check if parent is smaller than child, then swap.
if (list[parent] < list[child]) makeSwap(list, child, parent)
}
def siftDown (list, start, end) {
//end represents the limit of how far down the heap to sift
//start is the head of the heap
def parent = start
while (parent*2 < end) { //While the root has at least one child
def child = parent*2 + 1 //root*2+1 points to the left child
//find the child with the higher value
//if the child has a sibling and the child's value is less than its sibling's..
if (child + 1 <= end && list[child] < list[child+1]) child++ //point to the other child
if (checkSwap(list, child, parent)) { //check if parent is smaller than child and swap
parent = child //make child to next parent
} else {
return //The rest of the heap is in order - return.
}
}
}
def heapify (list) {
// Create a heap out of a list
// run through all the heap parents and
// ensure that each parent is lager than the child for all parent/childs.
// (list.size() -2) / 2 = last parent in the heap.
for (start in ((list.size()-2).intdiv(2))..0 ) {
siftDown(list, start, list.size() - 1)
}
}
def heapSort (list) {
//heap sort any unsorted list
heapify(list) //ensure that the list is in a binary heap state
//Run the list backwards and
//for end = (size of list -1 ) to 0
for (end in (list.size()-1)..0 ) {
makeSwap(list, 0, end) //put the top of the heap to the end (largest element)
siftDown(list, 0, end-1) //ensure that the rest is a heap again
}
list
}</syntaxhighlight>
Test:
<syntaxhighlight lang="groovy">println (heapSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4]))
Line 2,926 ⟶ 2,983:
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">data Tree a = Nil
| Node a (Tree a) (Tree a)
deriving Show
insert :: Ord a => a -> Tree a -> Tree a
insert x Nil = Node x Nil Nil
insert x (Node y leftBranch rightBranch)
| x < y = Node x (insert y rightBranch) leftBranch
| otherwise = Node y (insert x rightBranch) leftBranch
merge :: Ord a => Tree a -> Tree a -> Tree a
merge Nil t = t
merge t Nil = t
merge tx@(Node vx lx rx) ty@(Node vy ly ry)
| vx < vy = Node vx (merge lx rx) ty
| otherwise = Node vy tx (merge ly ry)
fromList :: Ord a => [a] -> Tree a
fromList = foldr insert Nil
toList :: Ord a => Tree a -> [a]
toList Nil = []
toList (Node x l r) = x : toList (merge l r)
heapSort :: Ord a => [a] -> [a]
heapSort = toList . fromList</syntaxhighlight>
e.g
<syntaxhighlight lang="haskell">ghci> heapSort [9,5,8,2,1,4,6,3,0,7]
[0,1,2,3,4,5,6,7,8,9]
</syntaxhighlight>
Using package [http://hackage.haskell.org/package/fgl fgl] from HackageDB
<syntaxhighlight lang="haskell">import Data.Graph.Inductive.Internal.Heap(
Line 2,940 ⟶ 3,031:
where (x,r) = (findMin h,deleteMin h)
e.g.
<syntaxhighlight lang="haskell">*Main> heapsort [[6,9],[2,13],[6,8,14,9],[10,7],[5]]
Line 5,495 ⟶ 5,586:
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func sift_down(a, start, end) {
var root = start
while ((2*root + 1) <= end) {
var child = (2*root + 1)
if ((child+1 <= end) && (a[child] < a[child + 1])) {
child += 1
}
if (a[root] < a[child]) {
a[child, root] = a[root, child]
root = child
} else {
return
}
}
}
func heapify(a, count) {
var start = ((count - 2) / 2)
while (start >= 0) {
sift_down(a, start, count-1)
start -= 1
}
}
func heap_sort(a, count) {
heapify(a, count)
var end = (count - 1)
while (end > 0) {
a[0, end] = a[end, 0]
end -= 1
sift_down(a, 0, end)
}
Line 5,529 ⟶ 5,620:
}
var arr = (1..10 -> shuffle)
say arr
heap_sort(arr, arr.len)
say arr
{{out}}
<pre>[10, 5, 2, 1, 7, 6, 4, 8, 3, 9]
Line 6,129 ⟶ 6,220:
=={{header|Wren}}==
<syntaxhighlight lang="
var root = start
while (root*2 + 1 <= end) {
Line 6,166 ⟶ 6,257:
}
var
for (a in
System.print("Before: %(a)")
heapSort.call(a)
Line 6,185 ⟶ 6,276:
Alternatively, we can just call a library method.
{{libheader|Wren-sort}}
<syntaxhighlight lang="
var
for (a in
System.print("Before: %(a)")
Sort.heap(a)
Line 6,199 ⟶ 6,290:
As above.
</pre>
=={{header|XPL0}}==
<syntaxhighlight lang "XPL0">proc HeapSort(Array, Size);
int Array, Size;
int First, Last, T;
proc Sift(First, Count);
int First, Count;
int Root, Child, T;
[Root:= First;
loop [if Root*2 + 1 >= Count then quit;
Child:= Root*2 + 1;
if Child < Count-1 and Array(Child) < Array(Child+1) then
Child:= Child+1;
if Array(Root) < Array(Child) then
[T:= Array(Root); Array(Root):= Array(Child); Array(Child):= T;
Root:= Child;
]
else quit;
];
];
[First:= (Size-1)/2 - 1;
Last:= Size-1;
while First >= 0 do
[Sift(First, Size-1);
First:= First-1;
];
while Last > 0 do
[T:= Array(Last); Array(Last):= Array(0); Array(0):= T;
Sift(0, Last);
Last:= Last-1;
];
];
int Array, Size, I;
[Array:= [4, 65, 2, 31, 0, 99, 2, 8, 3, 782, 1];
Size:= 11;
HeapSort(Array, Size);
for I:= 0, Size-1 do
[IntOut(0, Array(I)); ChOut(0, ^ )];
]</syntaxhighlight>
{{out}}
<pre>
0 1 2 2 3 4 8 31 65 99 782 </pre>
=={{header|zkl}}==
| |||