0
\$\begingroup\$

This is an implementation of heapsort as seen on Programming Pearls, adapted for java List collections. It is working on a copy of the list passed-in on purpose at the moment.

import java.util.ArrayList;
import java.util.List;

public final class HeapSort {

    private HeapSort() {}

    public static <T extends Comparable<T>> List<T> heapSort(List<T> unsortedList) {
        assert unsortedList != null;
        assert unsortedList.size() > 1;
        List<T> sortedList = new ArrayList<T>(unsortedList);
        for (int i = 1; i < sortedList.size(); i++) {
            sortedList = siftUp(sortedList, i);
        }
        for (int i = sortedList.size() - 1; i >= 1; i--) {
            sortedList = swap(sortedList, 0, i);
            sortedList = siftDown(sortedList, i - 1);
        }
        return sortedList;
    }

    private static <T extends Comparable<T>> List<T> siftUp(List<T> unsortedList, int n) {
        assert n > 0;
        for (int i = n;;) {
            if (i == 0) {
                break;
            }
            int p = i / 2;
            if (unsortedList.get(p).compareTo(unsortedList.get(i)) >= 0) {
                break;
            }
            unsortedList = swap(unsortedList, i, p);
            i = p;
        }
        return unsortedList;
    }

    private static <T extends Comparable<T>> List<T> siftDown(List<T> unsortedList, int n) {
        for (int i = 0;;) {
            int c = 2 * (i + 1) - 1;

            if (c > n) {
                break;
            }
            if (c + 1 <= n) {
                if (unsortedList.get(c + 1).compareTo(unsortedList.get(c)) > 0) {
                    c += 1;
                }
            }
            if (unsortedList.get(i).compareTo(unsortedList.get(c)) >= 0) {
                break;
            }
            unsortedList = swap(unsortedList, i, c);
            i = c;
        }
        return unsortedList;
    }

    private static <T> List<T> swap(List<T> list, int firstIndex, int secondIndex) {
        assert list != null;
        assert list.size() > 0;
        assert 0 <= firstIndex;
        assert firstIndex < list.size();
        assert 0 <= secondIndex;
        assert secondIndex < list.size();
        if (firstIndex == secondIndex) {
            return list;
        }
        T tmpT = list.get(secondIndex);
        list.set(secondIndex, list.get(firstIndex));
        list.set(firstIndex, tmpT);
        return list;
    }
}

Should I assert on list size in softDown and siftUp? Is the passing back and forth of list references ok?

\$\endgroup\$
1
\$\begingroup\$
for (int i = n;;) {
    if (i == 0) {
        break;
    }

This look very odd instead you can do

for(int i = n; i > 0;){

Asserts are kinda useless in java, they only work when the jvm is started with the -ea flag (or you do some reflection). instead just test and throw the IllegalArgumentException in the public method and remove the obvious assertions that would throw anyway.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ For private methods I most often rely on asserts actually; builds should always have the enable flag turned on. I keep other runtime exceptions for exposed methods. That's said, let me rephrase my question to: does it makes sense to wrap runtime exceptions with assert exceptions in this case, just to make it evident/readable it is an input validation? \$\endgroup\$ – guido Feb 11 '15 at 13:02
  • \$\begingroup\$ The accepted pattern for input validation is an if(check)throw at the top of the method \$\endgroup\$ – ratchet freak Feb 11 '15 at 13:04

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.