Sorting an array of primitives with a custom comparator and without conversion to objects

Question

What is the easiest way to sort a primitive array in Java using the specialized comparator (or key) function and without converting to an array of objects (for performance †).

† (Just a precaution, I am not asking if converting to objects is a good solution from POV performance.)

Answer 1

Sorting an array of primitive values ​​using a special comparator is not supported by standard Java libraries.

You can easily implement your simple sorting (e.g. bubblesort - O(N^2) ) from scratch, but the problem is that with sufficiently large arrays, the savings you make without converting to unit types are lost in a less efficient sorting algorithm .

So your choice:

• Implement high-performance sorting (merging, modified quicksort, etc.) from scratch.

• Find the existing high-performance sorting for primitive types that do not support comparators, and modify it.

• See if you can find a suitable third-party library that supports ptimitive arrays and comparators. (I could not find one ...)

(Note: the Comparator interface will not work here. It is not suitable for comparing primitive types.)

Answer 2

In Java 8, you can use your sort method to interface functions. This is the modified code from OpenJDK (Copyright 1997-2007 Sun Microsystems, Inc. GPLv2 ):

 import java.util.function.LongBinaryOperator; public class ArraySort { public static void sort(long[] x, LongBinaryOperator op) { sort1(x, 0, x.length, op); } private static void sort1(long x[], int off, int len, LongBinaryOperator op) { if (len < 7) { for (int i=off; i<len+off; i++) // Use custom comparator for insertion sort fallback for (int j=i; j>off && (op.applyAsLong(x[j-1], x[j]) > 0); j--) swap(x, j, j-1); return; } int m = off + (len >> 1); if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, ms, m, m+s); n = med3(x, n-2*s, ns, n); } m = med3(x, l, m, n); } long v = x[m]; int a = off, b = a, c = off + len - 1, d = c; while(true) { // Use custom comparator for checking elements while (b <= c && (op.applyAsLong(x[b], v) <= 0)) { if (x[b] == v) swap(x, a++, b); b++; } // Use custom comparator for checking elements while (c >= b && (op.applyAsLong(x[c], v) >= 0)) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } int s, n = off + len; s = Math.min(a-off, ba ); vecswap(x, off, bs, s); s = Math.min(dc, nd-1); vecswap(x, b, ns, s); if ((s = ba) > 1) sort1(x, off, s, op); if ((s = dc) > 1) sort1(x, ns, s, op); } private static void swap(long x[], int a, int b) { long t = x[a]; x[a] = x[b]; x[b] = t; } private static void vecswap(long x[], int a, int b, int n) { for (int i=0; i<n; i++, a++, b++) swap(x, a, b); } private static int med3(long x[], int a, int b, int c) { return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) : (x[b] > x[c] ? b : x[a] > x[c] ? c : a)); } } 

And call it using lambdas or something else that implements the LongBinaryOperator interface:

 import java.util.Arrays; public class Main { public static void main(String[] args) { long x[] = {5, 5, 7, 1, 2, 5, 8, 9, 23, 5, 32, 45, 76}; ArraySort.sort(x, (a, b) -> b - a); // sort descending System.out.println(Arrays.toString(x)); } } 

Output:

 [76, 45, 32, 23, 9, 8, 7, 5, 5, 5, 5, 2, 1] 

Answer 3

You can simply create your own comparison functions, and use one of the sorting algorithms.

simplest and slowest: BubbleSort (O (N ^ 2)).

harder but faster: MergeSort ((O (Nlog (n)).

now in both algos you have a part that asks if A> B, in this part you should put your comparison function.

 boolean compare(int x, int y){ if(/* your crazy compare condition */) return true; else return false; } 

example in sorting bubbles:

  procedure bubbleSort( A : list of sortable items ) repeat swapped = false for i = 1 to length(A) - 1 inclusive do: /* if this pair is out of order */ if compare(A[i],A[i-1]) then // Notcie the compare instead of A[i] > A[i-1] /* swap them and remember something changed */ swap( A[i-1], A[i] ) swapped = true end if end for until not swapped end procedure 

hope this helps

Answer 4

Create an Integer list representing the indices in the array, sort the list. You can reuse the list of indexes for different views.

Answer 5

I copied the following from Java 6 Arrays.java and modified it to suit my needs. It uses insertion sorting for smaller arrays, so it should be faster than pure quicksort.

 /** * Sorts the specified sub-array of integers into ascending order. */ private static void sort1(int x[], int off, int len) { // Insertion sort on smallest arrays if (len < 7) { for (int i=off; i<len+off; i++) for (int j=i; j>off && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } // Choose a partition element, v int m = off + (len >> 1); // Small arrays, middle element if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { // Big arrays, pseudomedian of 9 int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, ms, m, m+s); n = med3(x, n-2*s, ns, n); } m = med3(x, l, m, n); // Mid-size, med of 3 } int v = x[m]; // Establish Invariant: v* (<v)* (>v)* v* int a = off, b = a, c = off + len - 1, d = c; while(true) { while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } // Swap partition elements back to middle int s, n = off + len; s = Math.min(a-off, ba ); vecswap(x, off, bs, s); s = Math.min(dc, nd-1); vecswap(x, b, ns, s); // Recursively sort non-partition-elements if ((s = ba) > 1) sort1(x, off, s); if ((s = dc) > 1) sort1(x, ns, s); } /** * Swaps x[a] with x[b]. */ private static void swap(int x[], int a, int b) { int t = x[a]; x[a] = x[b]; x[b] = t; } /** * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */ private static void vecswap(int x[], int a, int b, int n) { for (int i=0; i<n; i++, a++, b++) swap(x, a, b); } /** * Returns the index of the median of the three indexed integers. */ private static int med3(int x[], int a, int b, int c) { return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) : (x[b] > x[c] ? b : x[a] > x[c] ? c : a)); }