Module org.cicirello.core
Package org.cicirello.util

Class SortingNetwork

java.lang.Object
org.cicirello.util.SortingNetwork
public final class SortingNetwork extends Object
Implements sorting networks for sorting small subsets of array elements.

  • Method Summary

    Modifier and Type
    Method
    Description
    static void
    compareExchange(double[] array, int minTargetIndex, int maxTargetIndex)
    The compare-exchange operation of sorting networks.
    static void
    compareExchange(int[] array, int minTargetIndex, int maxTargetIndex)
    The compare-exchange operation of sorting networks.
    static void
    sort(double[] array, int minTargetIndex, int medianTargetIndex, int maxTargetIndex)
    3-element sorting network.
    static void
    sort(int[] array, int minTargetIndex, int medianTargetIndex, int maxTargetIndex)
    3-element sorting network.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • compareExchange

      public static void compareExchange(double[] array, int minTargetIndex, int maxTargetIndex)
      The compare-exchange operation of sorting networks. Compares two elements, swapping them if out of order. Assumes the indexes are in bounds. No elements other than the two specified elements change.
      Parameters:
      array - the array to apply the compare-exchange
      minTargetIndex - the target index for the minimum of the two elements
      maxTargetIndex - the target index for the maximum of the two elements
      Throws:
      ArrayIndexOutOfBoundsException - if either of the indexes are outside the bounds of the array

    • compareExchange

      public static void compareExchange(int[] array, int minTargetIndex, int maxTargetIndex)
      The compare-exchange operation of sorting networks. Compares two elements, swapping them if out of order. Assumes the indexes are in bounds. No elements other than the two specified elements change.
      Parameters:
      array - the array to apply the compare-exchange
      minTargetIndex - the target index for the minimum of the two elements
      maxTargetIndex - the target index for the maximum of the two elements
      Throws:
      ArrayIndexOutOfBoundsException - if either of the indexes are outside the bounds of the array

    • sort

      public static void sort(double[] array, int minTargetIndex, int medianTargetIndex, int maxTargetIndex)
      3-element sorting network. Assumes the indexes are different and in bounds. No elements other than the three specified elements change.

      This sorting network makes 3 comparisons. Assuming all initial orderings are equally likely, the average number of swaps is 1.167. The maximum swaps is 2.

      This sorting network uses the following sequence of compare-exchange operations, specified by indexes beginning at 0 and consecutive (the methods of this class enable specifying the indexes of the elements to sort): (0,2), (0,1), (1,2). Note that although other 3-element sorting networks are possible with the same number of compare-exchange operations, only those that begin with (0,2) minimize the average number of swaps.

      Parameters:
      array - the array to apply the compare-exchange
      minTargetIndex - the target index for the minimum of the three elements
      medianTargetIndex - the target index for the median of the three elements
      maxTargetIndex - the target index for the maximum of the three elements
      Throws:
      ArrayIndexOutOfBoundsException - if any of the indexes are outside the bounds of the array

    • sort

      public static void sort(int[] array, int minTargetIndex, int medianTargetIndex, int maxTargetIndex)
      3-element sorting network. Assumes the indexes are different and in bounds. No elements other than the three specified elements change.

      This sorting network makes 3 comparisons. Assuming all initial orderings are equally likely, the average number of swaps is 1.167. The maximum swaps is 2.

      This sorting network uses the following sequence of compare-exchange operations, specified by indexes beginning at 0 and consecutive (the methods of this class enable specifying the indexes of the elements to sort): (0,2), (0,1), (1,2). Note that although other 3-element sorting networks are possible with the same number of compare-exchange operations, only those that begin with (0,2) minimize the average number of swaps.

      Parameters:
      array - the array to apply the compare-exchange
      minTargetIndex - the target index for the minimum of the three elements
      medianTargetIndex - the target index for the median of the three elements
      maxTargetIndex - the target index for the maximum of the three elements
      Throws:
      ArrayIndexOutOfBoundsException - if any of the indexes are outside the bounds of the array