Skip to content

Instantly share code, notes, and snippets.

@onacit

onacit/SelectionSort.java

Last active October 24, 2021 06:21
Show Gist options
  • Save onacit/0dd925d3768fcd4f79494ae32905dc1b to your computer and use it in GitHub Desktop.
Save onacit/0dd925d3768fcd4f79494ae32905dc1b to your computer and use it in GitHub Desktop.
Download ZIP
Selection sort in Java
Raw
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");
}
}
Raw
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");
}
}
Raw
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");
}
}
Raw
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");
}
}
Raw
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");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment