package jsat.utils;

import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * Provides implementations of quicksort. This is for use to obtain explicitly 
 * desired behavior, as well as aovid overhead by explicitly allowing extra 
 * Lists when sorting that are swapped when the array/list being sorted is 
 * swapped. 
*
* This class exist solely for performance reasons. * * @author Edward Raff */ public class QuickSort { private QuickSort() { } private static int med3(double[] 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)); } private static int med3(float[] 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)); } protected static void vecswap(double[] x, int a, int b, int n) { for (int i = 0; i < n; i++) swap(x, a++, b++); } protected static void vecswap(float[] x, int a, int b, int n) { for (int i = 0; i < n; i++) swap(x, a++, b++); } private static void vecswap(double[] x, int a, int b, int n, Collection> paired) { for (int i = 0; i < n; i++) { for (List l : paired) Collections.swap(l, a, b); swap(x, a++, b++); } } private static void vecswap(float[] x, int a, int b, int n, Collection> paired) { for (int i = 0; i < n; i++) { for (List l : paired) Collections.swap(l, a, b); swap(x, a++, b++); } } public static void swap(double[] array, int i, int j) { double tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static void swap(float[] array, int i, int j) { float tmp = array[i]; array[i] = array[j]; array[j] = tmp; } /** * Conditional swap, only swaps the values if array[i] > array[j] * @param array the array to potentially swap values in * @param i the 1st index * @param j the 2nd index */ public static void swapC(double[] array, int i, int j) { double tmp_i= array[i]; double tmp_j = array[j]; if(tmp_i > tmp_j) { array[i] = tmp_j; array[j] = tmp_i; } } /** * * @param array the array to swap values in * @param i the 1st index * @param j the 2nd index * @param paired a collection of lists, every list will have its indices swapped as well */ public static void swap(double[] array, int i, int j, Collection> paired) { double t = array[i]; array[i] = array[j]; array[j] = t; for(List l : paired) Collections.swap(l, i, j); } /** * * @param array the array to swap values in * @param i the 1st index * @param j the 2nd index * @param paired a collection of lists, every list will have its indices swapped as well */ public static void swap(float[] array, int i, int j, Collection> paired) { float t = array[i]; array[i] = array[j]; array[j] = t; for(List l : paired) Collections.swap(l, i, j); } /** * Performs sorting based on the double values natural comparator. * {@link Double#NaN} values will not be handled appropriately. * * @param x the array to sort * @param start the starting index (inclusive) to sort * @param end the ending index (exclusive) to sort */ public static void sort(double[] x, int start, int end) { int a = start; int n = end-start; if (n < 7)/* Insertion sort on smallest arrays */ { insertionSort(x, a, end); return; } int pm = a + (n/2); /* Small arrays, middle element */ if (n > 7) { int pl = a; int pn = a + n - 1; if (n > 40) /* Big arrays, pseudomedian of 9 */ { int s = n / 8; pl = med3(x, pl, pl + s, pl + 2 * s); pm = med3(x, pm - s, pm, pm + s); pn = med3(x, pn - 2 * s, pn - s, pn); } pm = med3(x, pl, pm, pn); /* Mid-size, med of 3 */ } double pivotValue = x[pm]; int pa = a, pb = pa, pc = end - 1, pd = pc; while (true) { while (pb <= pc && x[pb] <= pivotValue) { if (x[pb] == pivotValue) swap(x, pa++, pb); pb++; } while (pc >= pb && x[pc] >= pivotValue) { if (x[pc] == pivotValue) swap(x, pc, pd--); pc--; } if (pb > pc) break; swap(x, pb++, pc--); } int s; int pn = end; s = Math.min(pa - a, pb - pa); vecswap(x, a, pb - s, s); s = Math.min(pd - pc, pn - pd - 1); vecswap(x, pb, pn - s, s); //recurse if ((s = pb - pa) > 1) sort(x, a, a+s); if ((s = pd - pc) > 1) sort(x, pn - s, pn); } /** * * @param x * @param start inclusive * @param end exclusive */ public static void insertionSort(double[] x, int start, int end) { for (int i = start; i < end; i++) for (int j = i; j > start && x[j - 1] > x[j]; j--) swap(x, j, j - 1); } /** * Performs sorting based on the double values natural comparator. * {@link Double#NaN} values will not be handled appropriately. * * @param x the array to sort * @param start the starting index (inclusive) to sort * @param end the ending index (exclusive) to sort * @param paired a collection of lists, every list will have its indices swapped as well */ public static void sort(double[] x, int start, int end, Collection> paired) { int a = start; int n = end-start; if (n < 7)/* Insertion sort on smallest arrays */ { for (int i = a; i < end; i++) for (int j = i; j > a && x[j - 1] > x[j]; j--) swap(x, j, j - 1, paired); return; } int pm = a + (n/2); /* Small arrays, middle element */ if (n > 7) { int pl = a; int pn = a + n - 1; if (n > 40) /* Big arrays, pseudomedian of 9 */ { int s = n / 8; pl = med3(x, pl, pl + s, pl + 2 * s); pm = med3(x, pm - s, pm, pm + s); pn = med3(x, pn - 2 * s, pn - s, pn); } pm = med3(x, pl, pm, pn); /* Mid-size, med of 3 */ } double pivotValue = x[pm]; int pa = a, pb = pa, pc = end - 1, pd = pc; while (true) { while (pb <= pc && x[pb] <= pivotValue) { if (x[pb] == pivotValue) swap(x, pa++, pb, paired); pb++; } while (pc >= pb && x[pc] >= pivotValue) { if (x[pc] == pivotValue) swap(x, pc, pd--, paired); pc--; } if (pb > pc) break; swap(x, pb++, pc--, paired); } int s; int pn = end; s = Math.min(pa - a, pb - pa); vecswap(x, a, pb - s, s, paired); s = Math.min(pd - pc, pn - pd - 1); vecswap(x, pb, pn - s, s, paired); //recurse if ((s = pb - pa) > 1) sort(x, a, a+s, paired); if ((s = pd - pc) > 1) sort(x, pn - s, pn, paired); } /** * Performs sorting based on the double values natural comparator. * {@link Double#NaN} values will not be handled appropriately. * * @param x the array to sort * @param start the starting index (inclusive) to sort * @param end the ending index (exclusive) to sort * @param paired a collection of lists, every list will have its indices swapped as well */ public static void sort(float[] x, int start, int end, Collection> paired) { int a = start; int n = end-start; if (n < 7)/* Insertion sort on smallest arrays */ { for (int i = a; i < end; i++) for (int j = i; j > a && x[j - 1] > x[j]; j--) swap(x, j, j - 1, paired); return; } int pm = a + (n/2); /* Small arrays, middle element */ if (n > 7) { int pl = a; int pn = a + n - 1; if (n > 40) /* Big arrays, pseudomedian of 9 */ { int s = n / 8; pl = med3(x, pl, pl + s, pl + 2 * s); pm = med3(x, pm - s, pm, pm + s); pn = med3(x, pn - 2 * s, pn - s, pn); } pm = med3(x, pl, pm, pn); /* Mid-size, med of 3 */ } double pivotValue = x[pm]; int pa = a, pb = pa, pc = end - 1, pd = pc; while (true) { while (pb <= pc && x[pb] <= pivotValue) { if (x[pb] == pivotValue) swap(x, pa++, pb, paired); pb++; } while (pc >= pb && x[pc] >= pivotValue) { if (x[pc] == pivotValue) swap(x, pc, pd--, paired); pc--; } if (pb > pc) break; swap(x, pb++, pc--, paired); } int s; int pn = end; s = Math.min(pa - a, pb - pa); vecswap(x, a, pb - s, s, paired); s = Math.min(pd - pc, pn - pd - 1); vecswap(x, pb, pn - s, s, paired); //recurse if ((s = pb - pa) > 1) sort(x, a, a+s, paired); if ((s = pd - pc) > 1) sort(x, pn - s, pn, paired); } }

Ads help maintain this website.