Hi I've looked around a bit and haven't been able to find any direct discussion of this question. Most seem to cover time complexity and the big O notation.
I'm wondering if and how the order of input into a heapsort algorithm will impact the number of comparisons needed to sort the input. For example, take a heapsort algorithm that sorts in ascending order (smallest to largest)....if I input a set of integers already ordered in this way (ascending) how many comparisons would it require compared to a set of input that is ordered in a descending manner (largest to smallest)? How about compared to a completely randomized set of the same numbers?
public class Heap {
// This class should not be instantiated.
private Heap() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param pq
* the array to be sorted
*/
public static void sort(Comparable[] pq) {
int N = pq.length;
for (int k = N / 2; k >= 1; k--)
sink(pq, k, N);
while (N > 1) {
exch(pq, 1, N--);
sink(pq, 1, N);
}
}
private static void sink(Comparable[] pq, int k, int N) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N && less(pq, j, j + 1))
j++;
if (!less(pq, k, j))
break;
exch(pq, k, j);
k = j;
}
}
private static boolean less(Comparable[] pq, int i, int j) {
return pq[i - 1].compareTo(pq[j - 1]) < 0;
}
private static void exch(Object[] pq, int i, int j) {
Object swap = pq[i - 1];
pq[i - 1] = pq[j - 1];
pq[j - 1] = swap;
}
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
}