CS3343/3341
 Analysis of Algorithms 
  Recording Exchanges  
   with Heapsort  

Recording the Exchanges While Sorting with Heapsort.

In this page we count the number of exchanges while carrying out heapsort on three types of arrays: in sorted order, in reverse sorted order, and in random order.

Suppose exchanges(order) represents the number of exchanges needed to sort an array using heapsort, where the array is ordered as given by order. Then the following results are usually true (always true except for random order):

Here is the program with edited output data:

Number of Exchanges Needed while Sorting with Heapsort
// HeapsortRec.java: record exchangesg
public class HeapsortRec {

   private int parent(int i) {return i/2;}
   private int left  (int i) {return 2*i;}
   private int right (int i) {return 2*i+1;}
   private int heapsize; // part of heap
   private int exch;
   private double seed1 = 7712345;
   private double seed2 = 4498765;
   private double seed;

   private void exchange(int[] A, int i,
         int largest) {
      int temp = A[i];
      A[i] = A[largest];
      A[largest] = temp;
      exch++;
   }

   private void maxHeapify(int[] A, int i) {
      int l = left(i);
      int r = right(i);
      int largest;
      if (l <= heapsize && A[l] > A[i])
         largest = l;
      else largest = i;
      if (r <= heapsize && A[r] > A[largest])
         largest = r;
      if (largest != i) {
         exchange(A, i, largest); 
         maxHeapify(A, largest);
      }
   }

   private void buildMaxHeap(int[] A) {
      heapsize = A.length - 1;
      for (int i = heapsize/2; i >= 1; i--)
         maxHeapify(A, i);
   } 
      
   public int heapsort(int[] A) {
      exch = 0;
      buildMaxHeap(A);
      for(int i = A.length -1; i >= 2; i--) {
         exchange(A, 1, i);
         heapsize--;
         maxHeapify(A, 1);
      }
      return exch;
   }

   // random: returns random x, a<=x<=b
   int random(int a, int b) {
      return (int)((b - a + 1)*rand() + a);
   }

   // rand: returns random uniform double x, 0 < x < 1
   double rand() {
      double a1 = 48271.0,      a2 = 40692.0,
             m = 2147483647.0,  m2 = 2147483399;
      double q1,                q2;
      double q, diff;
      seed1 = a1*seed1;         seed2 = a2*seed2;
      q1 = Math.floor(seed1/m); q2 = Math.floor(seed2/m2);
      seed1 = seed1 - q1*m;     seed2 = seed2 - q2*m2;
      // now combine results
      if ((diff = seed1 - seed2) < 0.0)
         diff = diff + m;
      q = Math.floor(diff/m);
      seed = diff - q*m;
      return(seed/m);
   }

   public static void main(String[] args) {
      HeapsortRec h = new HeapsortRec();
      for (int N = 100; N <= 10000000; N = N * 10) {
         System.out.print(N + "  ");
         int[] A = new int[N+1];
         for (int i = 1; i <= N; i++)
            A[i] = i;
         int recExch1 = h.heapsort(A);
         System.out.print(recExch1 + " ");
         for (int i = 1; i <= N; i++)
            A[i] = N - i + 1;
         int recExch2 = h.heapsort(A);
         System.out.print(recExch1/(double)recExch2 +" ");
         for (int i = 1; i <= N; i++)
            A[i] = h.random(1, 100*N);
         int recExch3 = h.heapsort(A);
         System.out.print(recExch1/(double)recExch3 +" ");
         System.out.println(recExch1/(N*Math.log(N)));
      }
   }
}
Output.
Number of Exchanges in Sorting
Sorting using Heapsort.
Counting the number of Exchanges.
ints in sorted, reverse sorted, and random order

       N    Sorted  RevOrder    Random  sorted/N*log(N)

     100       640       516       580  1.389742
    1000      9708      8316      9076  1.405376
   10000    131956    116696    124218  1.432694
  100000   1650854   1497434   1575002  1.433913
 1000000  19787792  18333408  19049612  1.432288
10000000 231881708 216912428 223833947  1.438642

Revision date: 2012-10-15. (Please use ISO 8601, the International Standard Date and Time Notation.)