Thread: Sorting algorithms, worst-case input

One good way to generate worst-case initial ordering is to use a genetic algorithm. Unlike brute-forcing, this can find an answer for thousands of items.

• Each individual is an initial order
• The fitness function is a function of the number of swaps, compares, actual time taken to sort etc
• Swap-over could consist of choosing a cut point and swapping the portion above that point
• Mutations are a simple swap

Of course the worst case for the algorithms you have to implement aren't that interesting. A genetic algorithm would be more suited to finding a very bad case for median-of-three QuickSort, or a variant of ShellSort etc.

Another question regarding sorting algorithms.

I've noticed that most minHeap implementations are maxHeap with the two inequality signs regarding tree items inversed, which makes sense and seems to work.

Can somebody put into simple words why minHeap takes so much more time than maxHeap?

EDIT: Nope, they take the same, as long as the functions are called the same way technically. And here's a question about something I was never told during the C++ course.

Why is...

Code:

//
// MinHeaps an array, supposed to be worst-case scenario for a HeapSort.
//
void minHeap(int a[], int N)
{
	for (int k = N/2; k > 0; k--) {
		upHeap(a, k, N);
	}
}

void upHeap(int a[], int k, int N)
{
	int T = a[k - 1];
	while (k <= N/2) { 
		int j = k + k;

		if ((j < N) && (a[j - 1] > a[j])) { 
			j++;
		}
		if (T <= a[j - 1]) {
			break;
		} else { 
			a[k - 1] = a[j - 1];
			k = j;
		}
	}
	a[k - 1] = T;
}

...a gazillion times faster than...

Code:

void minHeap(int a[], int N)
{
	for (int k = N/2; k > 0; k--) {
		int T = a[k - 1];
		while (k <= N/2) { 
			int j = k + k;

			if ((j < N) && (a[j - 1] > a[j])) { 
				j++;
			}
			if (T <= a[j - 1]) {
				break;
			} else { 
				a[k - 1] = a[j - 1];
				k = j;
			}
		}
		a[k - 1] = T;
	}
}

And yes, the only difference is that the first time whatever's inside the for loop is a separate function, the second time the function's code is copied into the for loop.

Are you sure they are being passed the same thing?
I see no reason one would ever be slightly faster than the other, except by minor differences in the compiled code, that basically comes down to luck. For a different compiler, it may very well be the other way around, or they may be equal in speed.

By the way, an already sorted array is a min-heap, so you could just use that as the worst case for HeapSort. Reverse sorted is correspondingly the best case.