Sort part of array with heapsort, bug

Question

Here is my code for a introsort. I have trouble getting the heapsort part of the code working.

partition() and sort() works like it should, but the heapsort part doesnt sort correctly. I get sorted arrays (size=10) like this:

10
18
26
35
25
39
49
49
57
89

There are mostly sorted, except for a few numbers. I am only trying to sort a part of the array in each heapsort() call.

public class IntroSort {

    public static void sort(int[] arrayToSort){     
        int depth = ((int) Math.log(arrayToSort.length))*2;
        sort(arrayToSort, depth, 0, arrayToSort.length-1);
    }

    private static void sort(int[] arrayToSort, int depth, int start, int end){
        int length = arrayToSort.length;
        if(length <= 1){
            return;
        }else if(depth == 0){
            heapSort(arrayToSort, start, end);
        }else{
            if(start >= end)
                return;
            int pivot = arrayToSort[(start + end)/2];
            int index =  partition(arrayToSort, start, end, pivot);
            sort(arrayToSort, depth-1, start, index-1);
            sort(arrayToSort, depth-1, index, end);
        }
    }

    private static void heapSort(int[] arrayToSort, int start, int end){
        for (int i = end / 2 - 1; i >= start; i--)
            heapify(arrayToSort, end, i);
        for (int i=end-1; i>=start; i--){
            int temp = arrayToSort[start];
            arrayToSort[start] = arrayToSort[i];
            arrayToSort[i] = temp;
            heapify(arrayToSort, i, start);
        }
    }

    private static void heapify(int[] arrayToSort, int n, int i){
        int largest = i;
        int l = 2*i + 1;
        int r = 2*i + 2;
        if (l < n && arrayToSort[l] > arrayToSort[largest])
            largest = l;
        if (r < n && arrayToSort[r] > arrayToSort[largest])
            largest = r;
        if (largest != i){
            int swap = arrayToSort[i];
            arrayToSort[i] = arrayToSort[largest];
            arrayToSort[largest] = swap;
            heapify(arrayToSort, n, largest);
        }
    }

    private static int partition(int[] arrayToSort, int start, int end, int pivot){
        while(start <= end){
            while(arrayToSort[start] < pivot){
                start++;
            }
            while(arrayToSort[end] > pivot){
                end--;
            }
            if(start <= end){
                int temp = arrayToSort[start];
                arrayToSort[start] = arrayToSort[end];
                arrayToSort[end] = temp;
                start++;
                end--;
            }
        }
        return start;
    }

}

Any ideas?

Answer 1

I recently wrote a code solving just that. Here's a link to my post.

I'll also paste the code here for simplicity:

def buildMaxHeap(arr, arrayLength, indexStart, attr):
    for i in range(arrayLength):

        # if child is bigger than parent
        if getattr(arr[indexStart + i], attr) > getattr(arr[indexStart + int((i - 1) / 2)], attr):
            j = i

            # swap child and parent until
            # parent is smaller
            while getattr(arr[indexStart + j], attr) > getattr(arr[indexStart + int((j - 1) / 2)], attr):
                (arr[indexStart + j],
                 arr[indexStart + int((j - 1) / 2)]) = (arr[indexStart + int((j - 1) / 2)], arr[indexStart + j])
                j = int((j - 1) / 2)


def heapSort(arr, arrayLength, indexStart, attr):
    buildMaxHeap(arr, arrayLength, indexStart, attr)

    for i in range(arrayLength - 1, 0, -1):

        # swap value of first indexed
        # with last indexed
        arr[indexStart + 0], arr[indexStart + i] = arr[indexStart + i], arr[indexStart + 0]

        # maintaining heap property
        # after each swapping
        j, index = 0, 0

        while True:
            index = 2 * j + 1

            # if left child is smaller than
            # right child point index variable
            # to right child
            if (index < (i - 1) and getattr(arr[indexStart + index], attr) < getattr(arr[indexStart + index + 1], attr)):
                index += 1

            # if parent is smaller than child
            # then swapping parent with child
            # having higher value
            if index < i and getattr(arr[indexStart + j], attr) < getattr(arr[indexStart + index], attr):
                arr[indexStart + j], arr[indexStart + index] = arr[indexStart + index], arr[indexStart + j]

            j = index
            if index >= i:
                break

Answer 2

Because your heapify method can not build a max-heap for just a portion of the input array.

Let's have a look at an example: consider you have an array of length 10 and you want to sort the portion from 3 to 6, you'll call heapSort(array, 3, 6), from your code:

private static void heapSort(int[] arrayToSort, int start, int end){
    for (int i = end / 2 - 1; i >= start; i--)
        heapify(arrayToSort, end, i);
    for (int i=end-1; i>=start; i--){
        int temp = arrayToSort[start];
        arrayToSort[start] = arrayToSort[i];
        arrayToSort[i] = temp;
        heapify(arrayToSort, i, start);
    }
}

It'll call heapify(array, 6, 2) in the first for loop at first step, then in your heapify implementation, you'll compare the 2nd element with the 5th and 6th element and even maybe swap it with one of the later two. So the 2nd element involved unexpected when you want to sort portion 3 to 6, and even maybe swapped with 5th or 6th element, which makes the result incorrect.

If you want to build a portionHeapSort, I think it could be better to build a heapSort firstly, then build portionHeapSort based on it like the code below:

private static void portionHeapSort(int[] arrayToSort, int start, int end) {
    // start and end both inclusive
    int[] subArray = Arrays.copyOfRange(arrayToSort, start, end + 1);
    heapSort(subArray);
    for (int i = start; i <= end; i++) {
        arrayToSort[i] = subArray[i - start];
    }
}

Hope this could be helpful to you :-)

Answer 3

Carlton, i ran your code on some arrays, and data in that arrays had been sorted. Can you give examples, where your algorithms didn't work correct.

int[] arr = new int[]{17,1,15,1,2,3,18,100,100,454};
    heapSort(arr, 0, arr.length);
    for (int i:arr)
        System.out.print(i+" ");

and in result i got:

1 1 2 3 15 17 18 100 100 454 

Process finished with exit code 0