Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- boolean compare(int x, int y){
- if(/* your crazy compare condition */)
- return true;
- else return false;
- }
- 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
- 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, m-s, m, m+s);
- n = med3(x, n-2*s, n-s, 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, b-a ); vecswap(x, off, b-s, s);
- s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
- if ((s = b-a) > 1)
- sort1(x, off, s, op);
- if ((s = d-c) > 1)
- sort1(x, n-s, 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));
- }
- }
- 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));
- }
- }
- [76, 45, 32, 23, 9, 8, 7, 5, 5, 5, 5, 2, 1]
- /**
- * 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, m-s, m, m+s);
- n = med3(x, n-2*s, n-s, 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, b-a ); vecswap(x, off, b-s, s);
- s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
- // Recursively sort non-partition-elements
- if ((s = b-a) > 1)
- sort1(x, off, s);
- if ((s = d-c) > 1)
- sort1(x, n-s, 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));
- }
- java.util.Arrays.sort(int[])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement