Selection sort in Java

SelectionSort.java

package p_0dd925d3768fcd4f79494ae32905dc1b;

import java.util.Comparator;
import java.util.List;

import static java.util.Objects.requireNonNull;

/**
 * A class implements <a href="https://en.wikipedia.org/wiki/Selection_sort">Selection sort</a>.
 *
 * @author Jin Kwon &lt;onacit_at_gmail.com&gt;
 * @see <a href="https://en.wikipedia.org/wiki/Selection_sort">Selection sort (Wikipedia)</a>
 */
// https://gist.github.com/0dd925d3768fcd4f79494ae32905dc1b.git"
public class SelectionSort {

    // ---------------------------------------------------------------------------------------------------------- byte[]
    public static void sort1(final byte[] a, final int fromIndex, final int toIndex) {
        SelectionSortArrayBytes.sort1(a, fromIndex, toIndex);
    }

    public static void sort1(final byte[] a) {
        sort1(a, 0, requireNonNull(a, "a is null").length);
    }

    public static void sort2(final byte[] a, final int fromIndex, final int toIndex) {
        SelectionSortArrayBytes.sort2(a, fromIndex, toIndex);
    }

    public static void sort2(final byte[] a) {
        sort2(a, 0, requireNonNull(a, "a is null").length);
    }

    public static void sort3(final byte[] a, final int fromIndex, final int toIndex) {
        SelectionSortArrayBytes.sort3(a, fromIndex, toIndex);
    }

    public static void sort3(final byte[] a) {
        sort3(a, 0, requireNonNull(a, "a is null").length);
    }

    // ------------------------------------------------------------------------------------------------------------- T[]
    // basic
    public static <T> void sort1(final T[] a, final int fromIndex, final int toIndex,
                                 final Comparator<? super T> comparator) {
        SelectionSortArrayObjects.sort1(a, fromIndex, toIndex, comparator);
    }

    // cocktail(double selection)
    public static <T> void sort2(final T[] a, final int fromIndex, int toIndex,
                                 final Comparator<? super T> comparator) {
        SelectionSortArrayObjects.sort2(a, fromIndex, toIndex, comparator);
    }

    // heap
    public static <T> void sort3(final T[] a, final int fromIndex, final int toIndex,
                                 final Comparator<? super T> comparator, final boolean parallel) {
        SelectionSortArrayObjects.sort3(a, fromIndex, toIndex, comparator, parallel);
    }

    // ------------------------------------------------------------------------------------------------------------ List
    public static <T> void sort1(final List<T> list, final Comparator<? super T> comparator) {
        SelectionSortList.sort1(list, comparator);
    }

    public static <T extends Comparable<? super T>> void sort1(final List<T> list) {
        sort1(list, Comparator.naturalOrder());
    }

    public static <T> void sort2(final List<T> list, final Comparator<? super T> comparator) {
        SelectionSortList.sort2(list, comparator);
    }

    public static <T extends Comparable<? super T>> void sort2(final List<T> list) {
        sort2(list, Comparator.naturalOrder());
    }

    public static <T> void sort3(final List<T> list, final Comparator<? super T> comparator) {
        SelectionSortList.sort3(list, comparator);
    }

    public static <T extends Comparable<? super T>> void sort3(final List<T> list) {
        sort3(list, Comparator.naturalOrder());
    }

    public static <T> void sort4(final List<T> list, final Comparator<? super T> comparator, final boolean parallel) {
        SelectionSortList.sort4(list, comparator, parallel);
    }

    public static <T extends Comparable<? super T>> void sort4(final List<T> list, final boolean parallel) {
        sort4(list, Comparator.naturalOrder(), parallel);
    }

    public static <T> void sort5(final List<T> list, final Comparator<? super T> comparator, final boolean parallel) {
        SelectionSortList.sort5(list, comparator, parallel);
    }

    public static <T extends Comparable<? super T>> void sort5(final List<T> list, final boolean parallel) {
        sort5(list, Comparator.naturalOrder(), parallel);
    }

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

    private SelectionSort() {
        throw new AssertionError("instantiation is not allowed");
    }
}

SelectionSortArrayBytes.java

package p_0dd925d3768fcd4f79494ae32905dc1b;

import java.util.PriorityQueue;
import java.util.Queue;

import static java.util.Objects.requireNonNull;

final class SelectionSortArrayBytes {

    // basic
    static void sort1(final byte[] a, final int fromIndex, final int toIndex) {
        SelectionSortUtils.rangeCheck(requireNonNull(a, "a is null").length, fromIndex, toIndex);
        for (int i = fromIndex; i < toIndex - 1; i++) {
            int c = i;
            for (int j = i + 1; j < toIndex; j++) {
                if (a[j] < a[c]) {
                    c = j;
                }
            }
            if (c != i) {
                final byte t = a[i];
                a[i] = a[c];
                a[c] = t;
            }
        }
    }

    // cocktail(double selection)
    static void sort2(final byte[] a, final int fromIndex, int toIndex) {
        SelectionSortUtils.rangeCheck(requireNonNull(a, "a is null").length, fromIndex, toIndex);
        for (int i = fromIndex; i < toIndex - 1; i++) {
            int m = i;
            int x = i;
            for (int j = i + 1; j < toIndex; j++) {
                if (a[j] < a[m]) {
                    m = j;
                }
                if (a[j] > a[x]) {
                    x = j;
                }
            }
            if (m != i) {
                final byte t = a[i];
                a[i] = a[m];
                a[m] = t;
                if (x == i) {
                    x = m;
                }
            }
            final int l = toIndex-- - 1;
            if (x != l) {
                final byte t = a[x];
                a[l] = a[x];
                a[l] = t;
            }
        }
    }

    // heap
    static void sort3(final byte[] a, final int fromIndex, final int toIndex) {
        SelectionSortUtils.rangeCheck(requireNonNull(a, "a is null").length, fromIndex, toIndex);
        if (a.length < 2) { // IllegalArgumentException in PriorityQueue(0, ...)
            return;
        }
        final Queue<Byte> queue = new PriorityQueue<>(a.length, Byte::compare);
        for (int i = fromIndex; i < toIndex; i++) {
            queue.add(a[i]);
        }
        for (int i = fromIndex; i < toIndex; i++) {
            a[i] = queue.poll();
        }
    }

    private SelectionSortArrayBytes() {
        throw new AssertionError("instantiation is not allowed");
    }
}

SelectionSortArrayObjects.java

package p_0dd925d3768fcd4f79494ae32905dc1b;

import java.util.AbstractQueue;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Optional;
import java.util.PriorityQueue;
import java.util.Queue;

import static java.util.Objects.requireNonNull;

final class SelectionSortArrayObjects {

    // basic
    static <T> void sort1(final T[] a, final int fromIndex, final int toIndex, final Comparator<? super T> comparator) {
        SelectionSortUtils.rangeCheck(requireNonNull(a, "a is null").length, fromIndex, toIndex);
        requireNonNull(comparator, "comparator is null");
        for (int i = fromIndex; i < toIndex - 1; i++) {
            int c = i;
            for (int j = i + 1; j < toIndex; j++) {
                if (comparator.compare(a[j], a[c]) < 0) {
                    c = j;
                }
            }
            if (c != i) {
                final T t = a[i];
                a[i] = a[c];
                a[c] = t;
            }
        }
    }

    // cocktail(double selection)
    static <T> void sort2(final T[] a, final int fromIndex, int toIndex, final Comparator<? super T> comparator) {
        SelectionSortUtils.rangeCheck(requireNonNull(a, "a is null").length, fromIndex, toIndex);
        requireNonNull(comparator, "comparator is null");
        for (int i = fromIndex; i < toIndex - 1; i++) {
            int m = i;
            int x = i;
            for (int j = i + 1; j < toIndex; j++) {
                if (comparator.compare(a[j], a[m]) < 0) {
                    m = j;
                }
                if (comparator.compare(a[j], a[x]) > 0) {
                    x = j;
                }
            }
            if (m != i) {
                final T t = a[i];
                a[i] = a[m];
                a[m] = t;
                if (x == i) {
                    x = m;
                }
            }
            final int l = toIndex-- - 1;
            if (x != l) {
                final T t = a[x];
                a[l] = a[x];
                a[l] = t;
            }
        }
    }

    // heap
    static <T> void sort3(final T[] a, final int fromIndex, final int toIndex, final Comparator<? super T> comparator,
                          final boolean parallel) {
        SelectionSortUtils.rangeCheck(requireNonNull(a, "a is null").length, fromIndex, toIndex);
        requireNonNull(comparator, "comparator is null");
        if (!parallel && a.length < 2) {
            return;
        }
        final Comparator<Optional<T>> wrapped = (o1, o2) -> comparator.compare(o1.orElse(null), o2.orElse(null));
        final Queue<Optional<T>> queue;
        if (parallel) {
            queue = Arrays.stream(a)
                    .parallel()
                    .map(Optional::ofNullable)
                    .collect(() -> new PriorityQueue<>(wrapped), PriorityQueue::offer, AbstractQueue::addAll);
        } else {
            queue = new PriorityQueue<>(a.length, wrapped);
            Arrays.stream(a)
                    .map(Optional::ofNullable)
                    .forEach(queue::offer);
        }
        for (int i = fromIndex; i < toIndex; i++) {
            a[i] = queue.poll().orElse(null);
        }
    }

    private SelectionSortArrayObjects() {
        throw new AssertionError("instantiation is not allowed");
    }
}

SelectionSortList.java

package p_0dd925d3768fcd4f79494ae32905dc1b;

import java.util.AbstractQueue;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.ListIterator;
import java.util.Optional;
import java.util.PriorityQueue;
import java.util.Queue;

import static java.util.Objects.requireNonNull;

final class SelectionSortList {

    // --------------------------------------------------------------------------------------------------------- sort1/2
    // basic using Collections#swap
    static <T> void sort1(final List<T> list, final Comparator<? super T> comparator) {
        requireNonNull(list, "list is null");
        requireNonNull(comparator, "comparator is null");
        for (int i = 0; i < list.size() - 1; i++) {
            int mi = i;
            T me = list.get(i);
            for (int j = i + 1; j < list.size(); j++) {
                final T ce = list.get(j);
                if (comparator.compare(ce, me) < 0) {
                    mi = j;
                    me = ce;
                }
            }
            if (mi > i) {
                Collections.swap(list, i, mi);
            }
        }
    }

    // basic with ListIterator / Collections#swap
    static <T> void sort2(final List<T> list, final Comparator<? super T> comparator) {
        requireNonNull(list, "list is null");
        requireNonNull(comparator, "comparator is null");
        if (list.isEmpty()) {
            return;
        }
        for (final ListIterator<T> i = list.subList(0, list.size() - 1).listIterator(); i.hasNext(); ) {
            final int mi = i.nextIndex();
            int ci = mi;
            T ce = i.next();
            for (final ListIterator<T> j = list.listIterator(mi + 1); j.hasNext(); ) {
                final int ji = j.nextIndex();
                final T je = j.next();
                if (comparator.compare(je, ce) < 0) {
                    ci = ji;
                    ce = je;
                }
            }
            if (ci > mi) {
                Collections.swap(list, mi, ci);
            }
        }
    }

    // ----------------------------------------------------------------------------------------------------------- sort3

    static <T> void sort3(final List<T> list, final Comparator<? super T> comparator) {
        requireNonNull(list, "list is null");
        requireNonNull(comparator, "comparator is null");
        if (list.isEmpty()) {
            return;
        }
        for (final ListIterator<T> i = list.subList(0, list.size() - 1).listIterator(); i.hasNext(); ) {
            int mi = i.nextIndex();
            T me = i.next();
            for (final ListIterator<T> j = list.listIterator(mi + 1); j.hasNext(); ) {
                final T ce = j.next();
                if (comparator.compare(ce, me) < 0) {
                    i.set(ce);
                    j.set(me);
                    me = ce;
                }
            }
        }
    }

    // --------------------------------------------------------------------------------------------------------- sort4/5
    // cocktail(double selection) using PriorityQueue; List#set
    static <T> void sort4(final List<T> list, final Comparator<? super T> comparator, final boolean parallel) {
        requireNonNull(list, "list is null");
        requireNonNull(comparator, "comparator is null");
        if (!parallel && list.size() < 2) {
            return;
        }
        final Comparator<Optional<T>> wrapped = (o1, o2) -> comparator.compare(o1.orElse(null), o2.orElse(null));
        final Queue<Optional<T>> queue;
        if (parallel) {
            queue = list.stream()
                    .parallel()
                    .map(Optional::ofNullable)
                    .collect(() -> new PriorityQueue<>(wrapped), PriorityQueue::offer, AbstractQueue::addAll);
        } else {
            queue = new PriorityQueue<>(list.size(), wrapped);
            list.stream()
                    .map(Optional::ofNullable)
                    .forEach(queue::offer);
        }
        for (int i = 0; i < list.size(); i++) {
            list.set(i, queue.poll().orElse(null));
        }
    }

    // cocktail(double selection) using PriorityQueue; ListIterator#set
    static <T> void sort5(final List<T> list, final Comparator<? super T> comparator, final boolean parallel) {
        requireNonNull(list, "list is null");
        requireNonNull(comparator, "comparator is null");
        if (!parallel && list.size() < 2) {
            return;
        }
        final Comparator<Optional<T>> wrapped = (o1, o2) -> comparator.compare(o1.orElse(null), o2.orElse(null));
        final Queue<Optional<T>> queue;
        if (parallel) {
            queue = list.stream()
                    .parallel()
                    .map(Optional::ofNullable)
                    .collect(() -> new PriorityQueue<>(wrapped), PriorityQueue::offer, AbstractQueue::addAll);
        } else {
            queue = new PriorityQueue<>(list.size(), wrapped);
            list.stream()
                    .map(Optional::ofNullable)
                    .forEach(queue::offer);
        }
        for (final ListIterator<T> i = list.listIterator(); i.hasNext(); ) {
            i.next();
            i.set(queue.poll().orElse(null));
        }
    }

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

    private SelectionSortList() {
        throw new AssertionError("instantiation is not allowed");
    }
}

SelectionSortUtils.java

package p_0dd925d3768fcd4f79494ae32905dc1b;

final class SelectionSortUtils {

    // copied from java.util.Arrays#rangeCheck
    static void rangeCheck(final int arrayLength, final int fromIndex, final int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }
        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(fromIndex);
        }
        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException(toIndex);
        }
    }

    private SelectionSortUtils() {
        throw new AssertionError("instantiation is not allowed");
    }
}