I am currently studying sorting algorithms and need to implement HeapSort and Introspective Sort.
I think I have implemented HeapSort successfully (the code works, tried on millions of random arrays with random sizes, always worked), here's my code:
public static <T extends Comparable<? super T>> void hsort(T[] a) {
int n = a.length;
if(n < 2) return;
/* Heapify */
for(int i = (n-2)/2; i >= 0; i--)
moveDown(a, i, n);
for(int i = n-1; i > 0; i--) {
swap(a, 0, i);
moveDown(a, 0, i);
}
}
And the moveDown code is:
private static <T extends Comparable <? super T>> void moveDown(T[] a, int i, int max) {
T e = a[i];
int j; /* Son index */
while((j = (2*i)+1) < max) {
if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest son */
if(e.compareTo(a[j]) >= 0) break;
a[i] = a[j];
i = j;
}
a[i] = e;
}
These 2 methods shuold work completely fine, I have tested them multiple times and I never encountered any problem.
I am also trying to start from those 2 methods and implement Introspective Sort, my code is something like this:
public static <T extends Comparable<? super T>> void introSort(T[] a) {
int size = a.length;
if(size < 2) return;
int log = Integer.SIZE - Integer.numberOfLeadingZeros(size);
introSort(a, 0, size-1, 2*log);
}
private static <T extends Comparable<? super T>> void introSort(T[] a, int min, int max, int lev) {
if(max - min < ISORT_THRESHOLD) isort(a, min, max); // Small intervall
else if(lev == 0) hsortAux(a, min, max); // HeapSort on Array Portion
else {
// QuickSort
while (min < max) {
lev--;
/* Tukey approximation */
int t = tukeyApproximation(a, min, max-1);
//t = min; Ignore this for now and read below this code
T p = a[t];
int i = min, j = max;
do {
while(a[i].compareTo(p) < 0) i++;
while(a[j].compareTo(p) > 0) j--;
if(i <= j) {
swap(a, i, j);
i++; j--;
}
} while(i <= j);
introSort(a, min, j, lev);
min = i;
}
}
}
I think that the code above is fine too assuming that the methods isort and hsortAux work fine. On my testing I noticed that it only fails when the heapsort is called. The code should work (the target is to make it work) both when I use the tukey approximation to determine the pivot index and when I choose a random pivot like for example always the first element of the array. The partitioning with the QuickSort should be correct because I have tried many quicksort implementation and they all work and, as I already said, the code works when heapsort is not called. The partitioning is actually a copypaste from a quicksort in another method which works perfectly.
I know for sure that the methods isort and tukeyApproximation work as intended because I have tested them alone and on quicksort implementations and they work just fine.
However I don't seem to be capable of implementing a heapsort (the method called hsortAux) that does its job only on an array portion between min and max. I have spent several hours looking for an answer here and on Google, I have tried to implement my own version by looking at others people's code but I have failed multiple times and here I am wasting your time :). Once I managed to make a working heapSort but it didn't seem to work when the pivot was not chosen by the tukey approximation (e.g. the first element of the array or a random one in the portion).
Here is my current hsortAux code, derived from the origianl hsortAux:
private static <T extends Comparable<? super T>> void hsortAux(T[] a, int min, int max) {
for(int i = (min + max - 1)/2 ; i >= min; i--)
moveDownAux(a, min, i, max+1);
for(int i = max; i > min; i--) {
swap(a, min, i);
moveDownAux(a, min, min, i);
}
}
moveDownAux is supposed to be the moveDown method that only works on an array portion however I really have no idea how to implement it, I have tried to use the previous moveDown method instead but it obviously doesn't work at all. When implementing moveDownAux I'm not even sure I need the variable called min.
Here is my current moveDownAux method:
private static <T extends Comparable<? super T>> void moveDownAux(T[] a, int min, int i, int max) {
T e = a[i];
int j; /* Son */
while((j = (2*i)+1) < max-1) {
if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest Son */
if(e.compareTo(a[j]) >= 0) break;
a[i] = a[j];
i = j;
}
a[i] = e;
}
Thanks in advance for your time and answers
So after few weeks of pain I managed to understand what was wrong. Everything seems to work fine with the following moveDownAux method:
private static <T extends Comparable<? super T>> void moveDownAux(T[] a, int min, int i, int max) {
T e = a[i];
int j;
while((j = (2*i)+1 - min) < max) {
if(j+1 < max && a[j+1].compareTo(a[j]) > 0) j++; /* Biggest son */
if(e.compareTo(a[j]) >= 0) break;
a[i] = a[j];
i = j;
}
a[i] = e;
}
All I did in the end was change the while condition, I'm still trying to figure out why now it works and before it didn't.
Thanks to everyone