I am trying to make a heapsort algorithm that uses the 0th index and works for arrays of integers.
My tests with different arrays indicated that the first part of heapsort that makes max heap works correctly. The sorting process seems to swap correct numbers in first 2 runs for {33, 12, 5, 85, 2, 10, 11} but then again swaps my last index. I can’t seem to find a bug even thou the sort part of the code seems simple enough. Thank you.
Before: [85, 33, 11, 12, 2, 10, 5]
After: [33, 12, 11, 5, 2, 10, 85]
After: [12, 10, 11, 5, 2, 33, 85]
After: [11, 10, 85, 5, 12, 33, 2]
After: [85, 10, 33, 11, 12, 5, 2]
After: [85, 10, 33, 11, 12, 5, 2]
After: [85, 12, 33, 11, 10, 5, 2]
After: [85, 12, 33, 11, 10, 5, 2]
[85, 12, 33, 11, 10, 5, 2]
package com.example.java;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] test = {33, 12, 5, 85, 2, 10, 11};
heap mit = new heap(test);
mit.heapsort(test);
System.out.println(Arrays.toString(mit.getPq()));
}
}
package com.example.java;
import java.util.Arrays;
public class heap {
int N = 0;
int[] pq = null;
public heap (int[] n) {
this.pq = new int[n.length];
for (int i = 0; i <n.length ; i++) {
pq[i] = n[i];
N = n.length;
}
}
public boolean less(int i, int j) {
return pq[i] < pq[j];
}
public void exchange(int i, int j) {
int a = pq[i];
pq[i] = pq[j];
pq[j] = a;
}
public int getN() {
return N;
}
public int[] getPq() {
return pq;
}
public void sink(int k) {
while ((2*k)+1 < this.N) {
int j = 2 * k + 1;
if (j+1 < this.N) {
if (less(j, j+1)) j++;
} if (less(k, j)) {
exchange(k, j);
k = j;
} else break;
}
}
public void heapsort(int[] a) {
int N = a.length;
for (int k = N/2; k >=0 ; k--) {
sink(k);
}
System.out.println("Before: " + Arrays.toString(pq));
while (N>0) {
N--;
exchange(0, N);
sink(0);
System.out.println("After: " + Arrays.toString(pq));
}
}
}
