1
\$\begingroup\$

I am learning algorithms by using Java. Here is an implementation of heapsort. Let me know if anything is wrong and and suggestion to improve the algorithm.

public class HeapSort {
    public int arr[];

    public HeapSort(int[] arr) {
        this.arr = arr;
    }

    // to make a heap
    public void makeHeap() {
        for (int i = 0; i < arr.length; i++) {
            // index of child element
            int index = i;
            while (index != 0) {
                int parent = (index - 1) / 2;
                if (arr[index] <= arr[parent]) break;
                // swap child element to its parent one
                int temp = arr[index];
                arr[index] = arr[parent];
                arr[parent] = temp;
                index = parent;
            }
        }
    }

    // to remove item from the top of the binary tree -> arr[0]
    public void removeTopItem(int count) {
        int a = arr[0];
        arr[0] = arr[count];
        arr[count] = a;
        int index = 0;
        count--;
        // to remake binary tree
        while (true) {
            int leftChild = index * 2 + 1;
            int rightChild = index * 2 + 2;

            // check the boundary
            if (rightChild > count) break;
            if (arr[index] > arr[leftChild] && arr[index] > arr[rightChild]) break;

            // to get greater parent
            int parentGreat = arr[rightChild] > arr[leftChild] ? rightChild : leftChild;

            // swap current item to its parent one
            int temp = arr[index];
            arr[index] = arr[parentGreat];
            arr[parentGreat] = temp;
            index = parentGreat;
        }
    }

    // sort using by heap
    public int[] heapSort() {
        // make a heap
        makeHeap();
        // sorting
        for (int i = arr.length - 1; i >= 0; i--) {
            removeTopItem(i);
        }
        return arr;
    }
}
\$\endgroup\$
  • \$\begingroup\$ (How about doc comments?) How did/do you test this? (Doubtful about if (rightChild > count) break;) \$\endgroup\$ – greybeard Dec 8 '17 at 8:49
  • \$\begingroup\$ I haven't created doc yet. I did test it, it is working well. if (rightChild > count) -> because as sorted part is stored on the right side, I don't have to check until the end of the array length \$\endgroup\$ – Bahodir Boydedayev Dec 8 '17 at 22:09
2
\$\begingroup\$

I did test it, it is working well. Well,

    System.out.println(Arrays.toString(
        new HeapSort(new int[] {3, 2, 1}).heapSort()));

isn't working.

  • document/comment your code.
    You commented (all public method) members, see above for standard tool support.
    For every non-trivial piece of code, what is the reason it is there, in the first place?
    Starting at the class-, if not package-level:

    /** HeapSort as a <code>java.util.function.UnaryOperator<T></code>.
     * Java & coding beginner's exercise
     *  in type design and algorithm implementation.
     * The general idea is to turn the array into a max-heap
     *  and repeatedly move the max item
     *  from the shrinking heap to its current end. 
     */
    class HeapSort<T> implements In_placeSorter<T> {
        @Override
        public T sort(T toBeSorted) {
            if (!(toBeSorted instanceof int[]))
                throw new IllegalArgumentException("int[] only, for now");
            comparables = (int[]) toBeSorted;
            return (T) sort();
        } …
    

    (note sort() not (doc)commented here: inherits from In_placeSorter<T>)

  • name things for what use they are. arr is horribly unspecific (used comparables instead).
  • don't make things more visible than they need to be. When in doubt, start with default/not specifying visibility:
    int comparables[];
  • pay attention to boundaries:
    neither the loop in makeHeap() nor the one in heapSort() need to handle index 0.
    More importantly, while it is true that a right child needs to exist to be handled: what about left?
  • trying to implement "the general idea" without looking what&how others have done is a great step in learning —
    please precede it by considering how do I know/check the specification is met?
  • asking how to improve the procedure is another great step in programming
    (professionals prefix a when and). Start with algorithm;
    Just don't try to force it - if nothing suggests itself, turn to something else temporarily, sleep on it, or now look what others have done and how, for heap-sort:

    • why do heapify()s start at the middle of the array?
    • what is to be gained from not comparing the item to be (re-)inserted while there are two children?

    Continue with coding: e.g., there are several instances where you exchange/swap elements: "factor out" a method/procedure

  • handle petty concerns last, if at all:
    Java arrays & java.util.Arrays don't come with a swap()? Use java.util.Collections.swap(java.util.List, int, int) as a template
    using a for-loop:
    for (int index = i, parent ; index != 0 ; index = parent) {…

Just in case:

/** Rearranges items in ascending "natural" order. */
interface In_placeSorter<T> extends java.util.function.UnaryOperator<T> {
    /** Rearranges items in ascending "natural" order.
     * @param toBeSorted items to be sorted
     * @return <code>toBeSorted</code> */
    T sort(T toBeSorted);
    @Override
    default T apply(T t) { return sort(t); }
}
\$\endgroup\$
  • \$\begingroup\$ Thank you so much ! .Yes, I am implementing with basic theory that I learnt from the book first and going through with codes that others have done. You gave me great feedback and suggestions. Everything is correct that you mentioned above. I will fix it and do my best, thanks ! \$\endgroup\$ – Bahodir Boydedayev Jan 4 '18 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.