Consider the following algorithm for sorting an array segment A[0..n-1]. In the

Question

Consider the following algorithm for sorting an array segment A[0..n-1]. In the first step the algorithm performs the bubble-up operation on the range [0..n-1] and it places the smallest item on position 0. In the second step it performs the bubble-down operation on the range [1..n-1] and it places the largest item on position n-1. In the third step it performs bubble-up operation on the range [1..n-2] and it places the second smallest item on position 1. In the fourth step it performs the bubble-down operation on the range [2..n-2] and it places the second largest item on position n-2. The algorithm continues alternating bubble-up and bubble-down operations until the range consists of a single field.

(i) What is the number of swap operations performed in the worse case? Explain.

(ii) What is the average number of swap operations performed by this algorithm? Explain.

Explanation / Answer

1*21+2*22+3*23+…+N*2N=(N-1)*2N+1+2.
procedure pushdown(first, last: integer);
var
r: integer;
begin
r := first;
while r <= last div 2 do
if last = 2*r then begin
if A[r].key > A[2*r].key then
swap(A[r],A[2*r]);
r := last
end
else
if A[r].key > A[2*r].key and
A[2*r].key <= A[2*r+1].key then begin
swap(A[r],A[2*r]);
r := 2*r
end
else if A[r].key > A[2*r+1].key and
A[2*r+1].key < A[2*r].key then begin
swap(A[r],A[2*r+1]);
r := 2*r+1
end
else
r := last
end; { pushdown }
procedure heapsort;
var
i: integer;
begin
for i := n div 2 downto 1 do
pushdown(i,n);
for i := n downto 2 do begin
swap(A[1],A[i]);
pushdown(1,i-1)
end
end; { heapsort }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.