We were given a heap sort in a pseudocode:
******* HEAP SORT *******
sift(A, l, r)
-------------
f <- l
s <- 2 * l
temp <- A[f]
found <- false
while not found and s <= r
if s < r and A[s-1] < A[s] then
s <- s+1
if temp >= A[s-1] then
found <- true
else
A[f-1] <- A[s-1]
f <- s
s <- 2 * f
A[f-1] <- temp
heapsort(A,N)
-------------
l <- N / 2 + 1
r <- N
while l > 1
l <- l - 1
sift(A, l, r)
while r > 1
temp <- A[0]
A[0] <- A[r-1]
A[r-1] <- temp
r <- r - 1
:~~~~~ Average case performance: O(23N Ln N)
:~~~~~ Worst case performance: O(26N Ln N)
A => array
N => size of array
l => left edge
r => right edge
f => father pointer
s => son pointerI put it in a java code:
//Heap Sort: sift() and heapsort()
private static void sift(int[] a, int leftEdge, int rightEdge)
{
int fatherPointer = leftEdge;
int sonPointer = 2 * leftEdge;
int temp = a[fatherPointer];
boolean found = false;
while(!found && sonPointer <= rightEdge)
{
if(sonPointer < rightEdge && a[sonPointer-1] < a[sonPointer])
sonPointer = sonPointer + 1;
if(temp >= a[sonPointer-1])
found = true;
else
a[fatherPointer-1] = a[sonPointer-1];
fatherPointer = sonPointer;
sonPointer = 2 * fatherPointer;
}//while(!found && sonPointer <= rightEdge)
a[fatherPointer-1] = temp;
}//private static void sift(int[] a, int leftEdge, int rightEdge)
public static void heapsort(int[] a, int n)
{
int leftEdge = n / 2 + 1;
int rightEdge = n;
int temp;
while(leftEdge > 1)
{
leftEdge = leftEdge - 1;
sift(a, leftEdge, rightEdge);
}//while(leftEdge > 1)
while(rightEdge > 1)
{
temp = a[0];
a[0] = a[rightEdge - 1];
a[rightEdge - 1] = temp;
rightEdge = rightEdge - 1;
}//while(rightEdge > 1)
}//public static void heapsort(int[] a, int n)but seems like there is a flaw somewhere, since it is not sorting right :o
Please, please, could anyone make some suggestions?
Thanx,
Waldis :cry:
