SylvanasSun
3/17/2017 - 10:35 AM
Some common sorting algorithm snippet.
Some common sorting algorithm snippet.
/**
* Shell Sort
*
* @author SylvanasSun
*
*/
public class Shell {
// This class should not be instantiated.
private Shell() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* the array to be sorted
*/
public static void sort(Comparable[] a) {
int h = 1;
while (h < a.length / 3) {
// h sequence 1,4,13,40,121,364,1093,...
h = h * 3 + 1;
}
while (h >= 1) {
for (int i = h; i < a.length; i++) {
// a[i] insert to a[i-h],a[i-2*h],a[i-3*h]...
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a, j, j - h);
}
}
h = h / 3;
}
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param comparator
* compare the comparator specifying the order
* @param a
* a the array to be sorted
*/
public static void sort(Comparator comparator, Object[] a) {
int h = 1;
while (h < a.length / 3) {
h = h * 3 + 1;
}
while (h >= 1) {
for (int i = h; i < a.length; i++) {
for (int j = i; j >= h && less(comparator, a[j], a[j - h]); j -= h) {
exch(a, j, j - h);
}
}
h = h / 3;
}
}
/**
* Print array elements to console
*
* @param a
* a the array element print to console
*/
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// test
public static void main(String[] args) {
String[] a = new Scanner(System.in).nextLine().split("\\s+");
Shell.sort(a);
Shell.print(a);
}
}/**
* Selection Sort
*
* @author SylvanasSun
*
*/
public class Selection {
// This class should not be instantiated
private Selection() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* a the array to be sorted
*/
public static void sort(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
int min = i; // the smallest element index
for (int j = i + 1; j < a.length; j++) {
if (less(a[j], a[min]))
min = j;
exch(a, i, min);
}
}
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param comparator
* compare the comparator specifying the order
* @param a
* a the array to be sorted
*/
public static void sort(Comparator comparator, Object[] a) {
for (int i = 0; i < a.length; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (less(comparator, a[j], a[min]))
min = j;
exch(a, i, min);
}
}
}
/**
* Print array elements to console
*
* @param a
* a the array element print to console
*/
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// test
public static void main(String[] args) {
String[] s = new Scanner(System.in).nextLine().split("\\s+");
Selection.sort(s);
Selection.print(s);
}
}/**
* Quick Sort using three-way split
*
* @author SylvanasSun
*
*/
public class Quick3way {
// This class should not be instantiated.
private Quick3way() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* a the array to be sorted
*/
public static void sort(Comparable[] a) {
shuffle(a);
sort(a, 0, a.length - 1);
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param comparator
* compare the comparator specifying the order
* @param a
* a the array to be sorted
*/
public static void sort(Comparator comparator, Object[] a) {
shuffle(a);
sort(a, 0, a.length - 1, comparator);
}
/**
* Print array elements to console
*
* @param a
* a the array element print to console
*/
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// quicksort the subarray a[lo .. hi] using 3-way partitioning
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
int lt = lo, i = lo + 1, gt = hi;
Comparable v = a[lo]; // partition element
// a[lo..lt-1] < a[lt..gt] < a[gt+1..hi]
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) {
exch(a, i++, lt++);
} else if (cmp > 0) {
exch(a, i, gt--);
} else {
i++;
}
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
private static void sort(Object[] a, int lo, int hi, Comparator comparator) {
if (hi <= lo)
return;
int lt = lo, i = lo + 1, gt = hi;
Object v = a[lo]; // partition element
// a[lo..lt-1] < a[lt..gt] < a[gt+1..hi]
while (i <= gt) {
int cmp = comparator.compare(a[i], v);
if (cmp < 0) {
exch(a, i++, lt++);
} else if (cmp > 0) {
exch(a, i, gt--);
} else {
i++;
}
}
sort(a, lo, lt - 1, comparator);
sort(a, gt + 1, hi, comparator);
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// random sort an array
private static void shuffle(Object[] a) {
if (a == null)
throw new IllegalArgumentException("array is null.");
Random random = new Random();
int N = a.length;
for (int i = 0; i < N; i++) {
int j = i + random.nextInt(N - i);
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
public static void main(String[] args) {
String[] a = new Scanner(System.in).nextLine().split("\\s+");
Quick3way.sort(a);
Quick3way.print(a);
}
}/**
* Quick Sort
*
* @author SylvanasSun
*
*/
public class Quick {
// This class should not be instantiated.
private Quick() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* a the array to be sorted
*/
public static void sort(Comparable[] a) {
shuffle(a);
sort(a, 0, a.length - 1);
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param comparator
* compare the comparator specifying the order
* @param a
* a the array to be sorted
*/
public static void sort(Comparator comparator, Object[] a) {
shuffle(a);
sort(a, 0, a.length - 1, comparator);
}
/**
* Print array elements to console
*
* @param a
* a the array element print to console
*/
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo; // left point
int j = hi + 1; // right point
Comparable v = a[lo]; // partition element
while (true) {
// scan left point
while (less(a[++i], v)) {
if (i == hi)
break;
}
// scan right point
while (less(v, a[--j])) {
if (j == lo)
break;
}
// check if point cross
if (i >= j)
break;
exch(a, i, j);
}
// put partition element v to a[j]
exch(a, lo, j);
// now a[lo..j-1] <= a[j] <= a[j+1..hi]
return j;
}
private static int partition(Object[] a, int lo, int hi, Comparator comparator) {
int i = lo; // left point
int j = hi + 1; // right point
Object v = a[lo]; // partition element
while (true) {
// scan left point
while (less(comparator, a[++i], v)) {
if (i == hi)
break;
}
// scan right point
while (less(comparator, v, a[--j])) {
if (j == lo)
break;
}
// check if point cross
if (i >= j)
break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
int j = partition(a, lo, hi);
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
private static void sort(Object[] a, int lo, int hi, Comparator comparator) {
if (hi <= lo)
return;
int j = partition(a, lo, hi, comparator);
sort(a, lo, j - 1, comparator);
sort(a, j + 1, hi, comparator);
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// random sort an array
private static void shuffle(Object[] a) {
if (a == null)
throw new IllegalArgumentException("array is null.");
Random random = new Random();
int N = a.length;
for (int i = 0; i < N; i++) {
int j = i + random.nextInt(N - i);
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
// test
public static void main(String[] args) {
String[] a = new Scanner(System.in).nextLine().split("\\s+");
Quick.sort(a);
Quick.print(a);
}
}/**
* Merge Sort optimized using insertion handle small array.
*
* @author SylvanasSun
*
*/
public class MergeX {
private static final int CUTOFF = 7; // cutoff to insertion sort
// This class should not be instantiated.
private MergeX() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* the array to be sorted
*/
public static void sort(Comparable[] a) {
Comparable[] aux = a.clone();
sort(aux, a, 0, a.length - 1);
}
/**
* Rearranges the array in ascending order, using the provided order.
*
* @param a
* the array to be sorted
* @param comparator
* the comparator that defines the total order
*/
public static void sort(Object[] a, Comparator comparator) {
Object[] aux = a.clone();
sort(aux, a, 0, a.length - 1, comparator);
}
private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
dst[k] = src[j++];
} else if (j > hi) {
dst[k] = src[i++];
} else if (less(src[j], src[i])) {
dst[k] = src[j++];
} else {
dst[k] = src[i++];
}
}
}
private static void merge(Object[] src, Object[] dst, Comparator comparator, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
dst[k] = src[j++];
} else if (j > hi) {
dst[k] = src[i++];
} else if (less(comparator, src[j], src[i])) {
dst[k] = src[j++];
} else {
dst[k] = src[i++];
}
}
}
private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) {
// if (hi <= lo) return;
if (hi <= lo + CUTOFF) {
insertionSort(dst, lo, hi);
return;
}
int mid = lo + (hi - lo) / 2;
sort(dst, src, lo, mid);
sort(dst, src, mid + 1, hi);
// using System.arraycopy() is a bit faster than the above loop
if (!less(src[mid + 1], src[mid])) {
System.arraycopy(src, lo, dst, lo, hi - lo + 1);
return;
}
merge(src, dst, lo, mid, hi);
}
private static void sort(Object[] src, Object[] dst, int lo, int hi, Comparator comparator) {
if (hi <= lo + CUTOFF) {
insertionSort(dst, lo, hi, comparator);
return;
}
int mid = lo + (hi - lo) / 2;
sort(dst, src, lo, mid, comparator);
sort(dst, src, mid + 1, hi, comparator);
// using System.arraycopy() is a bit faster than the above loop
if (!less(comparator, src[mid + 1], src[mid])) {
System.arraycopy(src, lo, dst, lo, hi - lo + 1);
return;
}
merge(src, dst, comparator, lo, mid, hi);
}
// using insertion sort handle small array
private static void insertionSort(Comparable[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j > lo && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
private static void insertionSort(Object[] a, int lo, int hi, Comparator comparator) {
for (int i = lo; i <= hi; i++) {
for (int j = i; j > lo && less(comparator, a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
/**
* Print array elements to console
*
* @param a
* a the array element print to console
*/
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// test
public static void main(String[] args) {
String[] a = new Scanner(System.in).nextLine().split("\\s+");
MergeX.sort(a);
MergeX.print(a);
}
}/**
* Bottom-Up Merge Sort
*
* @author SylvanasSun
*
*/
public class MergeBU {
// This class should not be instantiated.
private MergeBU() {
};
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy a[] to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
private static void merge(Object[] a, Object[] aux, Comparator comparator, int lo, int mid, int hi) {
// copy a[] to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(comparator, aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* the array to be sorted
*/
public static void sort(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N];
for (int len = 1; len < N; len *= 2) {
for (int lo = 0; lo < N - len; lo += len + len) {
int mid = lo + len - 1;
int hi = Math.min(lo + len + len - 1, N - 1);
merge(a, aux, lo, mid, hi);
}
}
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param comparator
* compare the comparator specifying the order
* @param a
* a the array to be sorted
*/
public static void sort(Comparator comparator, Object[] a) {
int N = a.length;
Object[] aux = new Object[N];
for (int len = 1; len < N; len *= 2) {
for (int lo = 0; lo < N - len; lo += len + len) {
int mid = lo + len - 1;
int hi = Math.min(lo + len + len - 1, N - 1);
merge(a, aux, comparator, lo, mid, hi);
}
}
}
/**
* Print array elements to console
*
* @param a
* a the array element print to console
*/
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// test
public static void main(String[] args) {
String[] a = new Scanner(System.in).nextLine().split("\\s+");
MergeBU.sort(a);
MergeBU.print(a);
}
}/**
* Top-Down Merge Sort
*
* @author SylvanasSun
*
*/
public class Merge {
// This class should not be instantiated.
private Merge() {
}
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy a[] to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
private static void merge(Object[] a, Object[] aux, Comparator comparator, int lo, int mid, int hi) {
// copy a[] to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(comparator, aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
private static void sort(Object[] a, Object[] aux, Comparator comparator, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, comparator, lo, mid);
sort(a, aux, comparator, mid + 1, hi);
merge(a, aux, comparator, lo, mid, hi);
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* the array to be sorted
*/
public static void sort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param comparator
* compare the comparator specifying the order
* @param a
* a the array to be sorted
*/
public static void sort(Comparator comparator, Object[] a) {
Object[] aux = new Object[a.length];
sort(a, aux, comparator, 0, a.length - 1);
}
/**
* Print array elements to console
*
* @param a
* a the array element print to console
*/
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// test
public static void main(String[] args) {
String[] a = new Scanner(System.in).nextLine().split("\\s+");
Merge.sort(a);
Merge.print(a);
}
}/**
* Insertion Sort. class provides static methods for sorting an array using an
* optimized version of insertion sort (with half exchanges and a sentinel).
*
* @author SylvanasSun
*
*/
public class InsertionX {
// This class should not be instantiated.
private InsertionX() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* the array to be sorted
*/
public static void sort(Comparable[] a) {
int length = a.length;
// put smallest element in position to serve as sentinel
int exchanges = 0;
for (int i = length - 1; i > 0; i--) {
if (less(a[i], a[i - 1])) {
exch(a, i, i - 1);
exchanges++;
}
}
if (exchanges == 0)
return;
// insertion sort with half-exchanges
for (int i = 2; i < length; i++) {
Comparable v = a[i];
int j = i;
while (less(v, a[j - 1])) {
a[j] = a[j - 1];
j--;
}
a[j] = v;
}
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param comparator
* compare the comparator specifying the order
* @param a
* a the array to be sorted
*/
public static void sort(Comparator comparator, Object[] a) {
int length = a.length;
// put smallest element in position to serve as sentinel
int exchanges = 0;
for (int i = length - 1; i > 0; i--) {
if (less(comparator, a[i], a[i - 1])) {
exch(a, i, i - 1);
exchanges++;
}
}
if (exchanges == 0)
return;
// insertion sort with half-exchanges
for (int i = 2; i < length; i++) {
Object v = a[i];
int j = i;
while (less(comparator, v, a[j - 1])) {
a[j] = a[j - 1];
j--;
}
a[j] = v;
}
}
/**
* Print array elements to console
*
* @param a
* a the array element print to console
*/
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// test
public static void main(String[] args) {
String[] a = new Scanner(System.in).nextLine().split("\\s+");
InsertionX.sort(a);
InsertionX.print(a);
}
}/**
* Insertion Sort
*
* @author SylvanasSun
*
*/
public class Insertion {
// This class should not be instantiated
private Insertion() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* a the array to be sorted
*/
public static void sort(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
// a[i] insert to a[i-1]、a[i-2]、a[i-3]...
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param comparator
* compare the comparator specifying the order
* @param a
* a the array to be sorted
*/
public static void sort(Comparator comparator, Object[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = i; j > 0 && less(comparator, a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
/**
* Print array elements to console
*
* @param a
* a the array element print to console
*/
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// test
public static void main(String[] args) {
String[] s = new Scanner(System.in).nextLine().split("\\s+");
Insertion.sort(s);
Insertion.print(s);
}
}/**
* Bubble Sort
*
* @author SylvanasSun
*
*/
public class Bubble {
// This class should not be instantiated.
private Bubble() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* a the array to be sorted
*/
public static void sort(Comparable[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (less(a[j + 1], a[j])) {
exch(a, j, j + 1);
}
}
}
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param a
* a the arry to be sorted
* @param comparator
* comparator the comparator specifying the order
*/
public static void sort(Object[] a, Comparator comparator) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (less(comparator, a[j + 1], a[j])) {
exch(a, j, j + 1);
}
}
}
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// print array elements to console
public static void print(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// test
public static void main(String[] args) {
String[] s = new Scanner(System.in).nextLine().split("\\s+");
Bubble.sort(s);
Bubble.print(s);
}
}/**
* Insertion Sort class provides a static method for sorting an array using an
* optimized binary insertion sort with half exchanges.
*
* @author SylvanasSun
*
*/
public class BinaryInsertion {
// This class should not be instantiated.
private BinaryInsertion() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* the array to be sorted
*/
public static void sort(Comparable[] a) {
int length = a.length;
for (int i = 1; i < length; i++) {
// binary search to determine index j at which to insert a[i]
Comparable v = a[i];
int lo = 0, hi = i;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (less(v, a[mid]))
hi = mid;
else
lo = mid + 1;
}
// insertion sort with "half exchanges"
// (insert a[i] at index j and shift a[j], ..., a[i-1] to right)
for (int j = i; j > lo; --j)
a[j] = a[j - 1];
a[lo] = v;
}
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param comparator
* compare the comparator specifying the order
* @param a
* a the array to be sorted
*/
public static void sort(Comparator comparator, Object[] a) {
int length = a.length;
for (int i = 1; i < length; i++) {
// binary search to determine index j at which to insert a[i]
Object v = a[i];
int lo = 0, hi = 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (less(comparator, v, a[mid])) {
hi = mid;
} else {
lo = mid + 1;
}
}
// insertion sort with "half exchanges"
// (insert a[i] at index j and shift a[j],...,a[i-1] to right)
for (int j = i; j > lo; --j) {
a[j] = a[j - 1];
}
a[lo] = v;
}
}
/**
* Print array elements to console
*
* @param a
* a the array element print to console
*/
public static void print(Object[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// test
public static void main(String[] args) {
String[] a = new Scanner(System.in).nextLine().split("\\s+");
BinaryInsertion.sort(a);
BinaryInsertion.print(a);
}
}Some common sorting algorithm snippet.