InsertionSort.java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.stream.IntStream;

import static java.util.concurrent.ThreadLocalRandom.current;

class InsertionSort {

    /**
     * Checks whether elements in specified iterable is sorted by specified comparator.
     *
     * @param iterable   the iterable whose elements are checked
     * @param comparator the comparator for comparaing elements
     * @param <T>        element type parameter
     * @return {@code true} if elements in specified iterable are sorted; {@code false} otherwise.
     */
    private static <T> boolean isSorted(final Iterable<? extends T> iterable, final Comparator<? super T> comparator) {
        if (iterable == null) {
            throw new NullPointerException("iterable is null");
        }
        if (comparator == null) {
            throw new NullPointerException("comparator is null");
        }
        T previous = null;
        for (final T current : iterable) {
            if (previous != null && comparator.compare(previous, current) > 0) {
                return false;
            }
            previous = current;
        }
        return true;
    }

    /**
     * Checks whether elements in specified iterable is sorted in specified order.
     *
     * @param iterable the iterable whose elements are checked.
     * @param natural  {@code true} for natural ordering; {@code false} for reverse ordering.
     * @param <T>      element type parameter
     * @return {@code true} if elements in specified iterable are sorted; {@code false} otherwise
     * @see Comparator#naturalOrder()
     * @see Comparator#reverseOrder()
     * @see #isSorted(Iterable, Comparator)
     */
    private static <T extends Comparable<? super T>> boolean isSorted(final Iterable<? extends T> iterable,
                                                                      final boolean natural) {
        if (iterable == null) {
            throw new NullPointerException("iterable is null");
        }
        return isSorted(iterable, natural ? Comparator.naturalOrder() : Comparator.reverseOrder());
    }

    /**
     * Sorts specified list by using specified comparator for comparing elements. The {@code sort1} method uses indices
     * for manipulating the list.
     *
     * @param list       the list to be sorted
     * @param comparator a comparator for comparing elements in the list
     * @param <E>        element type parameter
     * @return the specified list.
     */
    public static <E> List<E> sort1(final List<E> list, final Comparator<? super E> comparator) {
        for (int i = 1; i < list.size(); i++) {
            for (int j = i; j > 0; j--) {
                if (comparator.compare(list.get(j - 1), list.get(j)) > 0) {
                    final E element = list.get(j);
                    list.set(j, list.get(j - 1));
                    list.set(j - 1, element);
                }
            }
        }
        if (!isSorted(list, comparator)) {
            System.out.println("not sorted: " + list);
        }
        return list;
    }

    /**
     * Sorts specified list using specified comparator for comparing elements. The {@code sort2} method uses {@link
     * ListIterator}s for manipulate the list.
     *
     * @param list       the list whose elements are sorted
     * @param comparator the comparator for comparing elements in the list
     * @param <E>        element type parameter
     * @return the specified list
     */
    public static <E> List<E> sort2(final List<E> list, final Comparator<? super E> comparator) {
        if (list.isEmpty()) {
            return list;
        }
        for (final ListIterator<E> i = list.listIterator(1); i.hasNext(); ) {
            final int nextIndex = i.nextIndex();
            final E next = i.next();
            for (final ListIterator<E> j = list.listIterator(nextIndex); j.hasPrevious(); ) {
                final int previousIndex = j.previousIndex();
                final E previous = j.previous();
                if (comparator.compare(previous, next) > 0) {
                    j.set(next);
                    i.set(previous);
                }
            }
        }
        if (!isSorted(list, comparator)) {
            System.out.println("not sorted: " + list);
        }
        return list;
    }

    private static <T extends List<? super Integer>> T fill(final T list) {
        IntStream.range(0, current().nextInt(5, 10)).forEach(i -> list.add(current().nextInt(0, 10)));
        return list;
    }

    public static void main(final String... args) {
        System.out.println(sort1(fill(new ArrayList<Integer>()), Comparator.<Integer>naturalOrder()));
        System.out.println(sort1(fill(new ArrayList<Integer>()), Comparator.<Integer>reverseOrder()));
        System.out.println(sort2(fill(new ArrayList<Integer>()), Comparator.<Integer>naturalOrder()));
        System.out.println(sort2(fill(new ArrayList<Integer>()), Comparator.<Integer>reverseOrder()));
        System.out.println(sort1(fill(new LinkedList<Integer>()), Comparator.<Integer>naturalOrder()));
        System.out.println(sort1(fill(new LinkedList<Integer>()), Comparator.<Integer>reverseOrder()));
        System.out.println(sort2(fill(new LinkedList<Integer>()), Comparator.<Integer>naturalOrder()));
        System.out.println(sort2(fill(new LinkedList<Integer>()), Comparator.<Integer>reverseOrder()));
    }

    // -----------------------------------------------------------------------------------------------------------------

    /**
     * Creates a new instance.
     */
    private InsertionSort() {
        super();
    }
}