Package com.irurueta.sorting

Class HeapsortSorter<T>

java.lang.Object
com.irurueta.sorting.Sorter<T>
com.irurueta.sorting.HeapsortSorter<T>
Type Parameters:
T - Type of instances being sorted.

This class is based on algorithm found at Numerical Recipes. 3rd Edition. Cambridge Press. Chapter 8. p. 428 Knuth. D.E. 1997, Sorting and Searching, 3rd ed., vol. 3 of The Art of Computer Programming (Reading, MA: Addison-Wesley) Sedgewick, R. 1998. Algorithms in C, 3rd ed. (Reading, MA: Addison- Wesley), Chapter 11.

public class HeapsortSorter<T> extends Sorter<T>
Sorts instances of type T in provided arrays using Heapsort method.

  • Field Summary

    Fields inherited from class com.irurueta.sorting.Sorter

    DEFAULT_SORTING_METHOD

  • Constructor Summary

    Constructors
    Constructor
    Description
    HeapsortSorter()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    SortingMethod
    getMethod()
    Returns sorting method of this class.
    private void
    siftDown(double[] ra, int l, int r, int fromIndex)
    Internal method to reorder sub-array ra.
    private void
    siftDown(float[] ra, int l, int r, int fromIndex)
    Internal method to reorder sub-array ra.
    private void
    siftDown(int[] ra, int l, int r, int fromIndex)
    Internal method to reorder sub-array ra.
    private void
    siftDown(long[] ra, int l, int r, int fromIndex)
    Internal method to reorder sub-array ra.
    private void
    siftDown(T[] ra, int l, int r, Comparator<T> comparator, int fromIndex)
    Internal method to reorder sub-array ra.
    private void
    siftDownWithIndices(double[] ra, int[] rb, int l, int r, int fromIndex)
    Internal method to reorder sub-array ra along with its corresponding indices.
    private void
    siftDownWithIndices(float[] ra, int[] rb, int l, int r, int fromIndex)
    Internal method to reorder sub-array ra along with its corresponding indices.
    private void
    siftDownWithIndices(int[] ra, int[] rb, int l, int r, int fromIndex)
    Internal method to reorder sub-array ra along with its corresponding indices.
    private void
    siftDownWithIndices(long[] ra, int[] rb, int l, int r, int fromIndex)
    Internal method to reorder sub-array ra along with its corresponding indices.
    private void
    siftDownWithIndices(T[] ra, int[] rb, int l, int r, Comparator<T> comparator, int fromIndex)
    Internal method to reorder sub-array ra along with its corresponding indices.
    void
    sort(double[] array, int fromIndex, int toIndex)
    Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
    void
    sort(float[] array, int fromIndex, int toIndex)
    Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
    void
    sort(int[] array, int fromIndex, int toIndex)
    Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
    void
    sort(long[] array, int fromIndex, int toIndex)
    Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
    void
    sort(T[] array, int fromIndex, int toIndex, Comparator<T> comparator)
    Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
    int[]
    sortWithIndices(double[] array, int fromIndex, int toIndex)
    Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
    int[]
    sortWithIndices(float[] array, int fromIndex, int toIndex)
    Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
    int[]
    sortWithIndices(int[] array, int fromIndex, int toIndex)
    Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
    int[]
    sortWithIndices(long[] array, int fromIndex, int toIndex)
    Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
    int[]
    sortWithIndices(T[] array, int fromIndex, int toIndex, Comparator<T> comparator)
    Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
    private void
    swapIndices(int[] indices, int posA, int posB)
    Swaps values in array of indices at locations posA and posB.

    Methods inherited from class com.irurueta.sorting.Sorter

    create, create, getInitialIndicesVector, median, median, median, median, median, median, median, median, median, median, median, median, select, select, select, select, select, select, select, select, select, select, select, select, sort, sort, sort, sort, sort, sort, sort, sortWithIndices, sortWithIndices, sortWithIndices, sortWithIndices, sortWithIndices, sortWithIndices, sortWithIndices, swap, swap, swap, swap, swap

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • HeapsortSorter

      public HeapsortSorter()

  • Method Details

    • sort

      public void sort(T[] array, int fromIndex, int toIndex, Comparator<T> comparator)
      Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.
      Specified by:
      sort in class Sorter<T>
      Parameters:
      array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.
      fromIndex - Index were sorting starts (inclusive).
      toIndex - Index were sorting stops (exclusive).
      comparator - Determines whether an element is greater or lower than another one.
      Throws:
      IllegalArgumentException - If fromIndex > toIndex.
      ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

    • sortWithIndices

      public int[] sortWithIndices(T[] array, int fromIndex, int toIndex, Comparator<T> comparator)
      Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.
      Specified by:
      sortWithIndices in class Sorter<T>
      Parameters:
      array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.
      fromIndex - Index were sorting starts (inclusive).
      toIndex - Index were sorting stops (exclusive).
      comparator - Determines whether an element is greater or lower than another one.
      Returns:
      Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.
      Throws:
      IllegalArgumentException - If fromIndex > toIndex.
      ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

    • getMethod

      public SortingMethod getMethod()
      Returns sorting method of this class.
      Specified by:
      getMethod in class Sorter<T>
      Returns:
      Sorting method.

    • sort

      public void sort(double[] array, int fromIndex, int toIndex)
      Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.
      Specified by:
      sort in class Sorter<T>
      Parameters:
      array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.
      fromIndex - Index were sorting starts (inclusive).
      toIndex - Index were sorting stops (exclusive).
      Throws:
      IllegalArgumentException - If fromIndex > toIndex.
      ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

    • sortWithIndices

      public int[] sortWithIndices(double[] array, int fromIndex, int toIndex)
      Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.
      Specified by:
      sortWithIndices in class Sorter<T>
      Parameters:
      array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.
      fromIndex - Index were sorting starts (inclusive).
      toIndex - Index were sorting stops (exclusive).
      Returns:
      Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.
      Throws:
      IllegalArgumentException - If fromIndex > toIndex.
      ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

    • sort

      public void sort(float[] array, int fromIndex, int toIndex)
      Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.
      Specified by:
      sort in class Sorter<T>
      Parameters:
      array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.
      fromIndex - Index were sorting starts (inclusive).
      toIndex - Index were sorting stops (exclusive).
      Throws:
      IllegalArgumentException - If fromIndex > toIndex.
      ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

    • sortWithIndices

      public int[] sortWithIndices(float[] array, int fromIndex, int toIndex)
      Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.
      Specified by:
      sortWithIndices in class Sorter<T>
      Parameters:
      array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.
      fromIndex - Index were sorting starts (inclusive).
      toIndex - Index were sorting stops (exclusive).
      Returns:
      Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.
      Throws:
      IllegalArgumentException - If fromIndex > toIndex.
      ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

    • sort

      public void sort(int[] array, int fromIndex, int toIndex)
      Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.
      Specified by:
      sort in class Sorter<T>
      Parameters:
      array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.
      fromIndex - Index were sorting starts (inclusive).
      toIndex - Index were sorting stops (exclusive).
      Throws:
      IllegalArgumentException - If fromIndex > toIndex.
      ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

    • sortWithIndices

      public int[] sortWithIndices(int[] array, int fromIndex, int toIndex)
      Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.
      Specified by:
      sortWithIndices in class Sorter<T>
      Parameters:
      array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.
      fromIndex - Index were sorting starts (inclusive).
      toIndex - Index were sorting stops (exclusive).
      Returns:
      Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.
      Throws:
      IllegalArgumentException - If fromIndex > toIndex.
      ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

    • sort

      public void sort(long[] array, int fromIndex, int toIndex)
      Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.
      Specified by:
      sort in class Sorter<T>
      Parameters:
      array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.
      fromIndex - Index were sorting starts (inclusive).
      toIndex - Index were sorting stops (exclusive).
      Throws:
      IllegalArgumentException - If fromIndex > toIndex.
      ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

    • sortWithIndices

      public int[] sortWithIndices(long[] array, int fromIndex, int toIndex)
      Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.
      Specified by:
      sortWithIndices in class Sorter<T>
      Parameters:
      array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.
      fromIndex - Index were sorting starts (inclusive).
      toIndex - Index were sorting stops (exclusive).
      Returns:
      Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.
      Throws:
      IllegalArgumentException - If fromIndex > toIndex.
      ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

    • siftDown

      private void siftDown(T[] ra, int l, int r, Comparator<T> comparator, int fromIndex)
      Internal method to reorder sub-array ra.
      Parameters:
      ra - sub-array ra.
      l - l value.
      r - r value.
      comparator - a comparator.
      fromIndex - initial position.

    • siftDownWithIndices

      private void siftDownWithIndices(T[] ra, int[] rb, int l, int r, Comparator<T> comparator, int fromIndex)
      Internal method to reorder sub-array ra along with its corresponding indices.
      Parameters:
      ra - sub-array ra.
      rb - sub-array rb.
      l - l value.
      r - r value.
      comparator - a comparator.
      fromIndex - initial position.

    • swapIndices

      private void swapIndices(int[] indices, int posA, int posB)
      Swaps values in array of indices at locations posA and posB.
      Parameters:
      indices - array containing indices to be swapped.
      posA - Location to be swapped.
      posB - Location to be swapped.

    • siftDown

      private void siftDown(double[] ra, int l, int r, int fromIndex)
      Internal method to reorder sub-array ra.
      Parameters:
      ra - sub-array ra.
      l - l value.
      r - r value.
      fromIndex - initial position.

    • siftDownWithIndices

      private void siftDownWithIndices(double[] ra, int[] rb, int l, int r, int fromIndex)
      Internal method to reorder sub-array ra along with its corresponding indices.
      Parameters:
      ra - sub-array ra.
      rb - sub-array rb.
      l - l value.
      r - r value.
      fromIndex - initial position.

    • siftDown

      private void siftDown(float[] ra, int l, int r, int fromIndex)
      Internal method to reorder sub-array ra.
      Parameters:
      ra - sub-array ra.
      l - l value.
      r - r value.
      fromIndex - initial position.

    • siftDownWithIndices

      private void siftDownWithIndices(float[] ra, int[] rb, int l, int r, int fromIndex)
      Internal method to reorder sub-array ra along with its corresponding indices.
      Parameters:
      ra - sub-array ra.
      rb - sub-array rb.
      l - l value.
      r - r value.
      fromIndex - initial position.

    • siftDown

      private void siftDown(int[] ra, int l, int r, int fromIndex)
      Internal method to reorder sub-array ra.
      Parameters:
      ra - sub-array ra.
      l - l value.
      r - r value.
      fromIndex - initial position.

    • siftDownWithIndices

      private void siftDownWithIndices(int[] ra, int[] rb, int l, int r, int fromIndex)
      Internal method to reorder sub-array ra along with its corresponding indices.
      Parameters:
      ra - sub-array ra.
      rb - sub-array rb.
      l - l value.
      r - r value.
      fromIndex - initial position.

    • siftDown

      private void siftDown(long[] ra, int l, int r, int fromIndex)
      Internal method to reorder sub-array ra.
      Parameters:
      ra - sub-array ra.
      l - l value.
      r - r value.
      fromIndex - initial value.

    • siftDownWithIndices

      private void siftDownWithIndices(long[] ra, int[] rb, int l, int r, int fromIndex)
      Internal method to reorder sub-array ra along with its corresponding indices.
      Parameters:
      ra - sub-array ra.
      rb - sub-array rb.
      l - l value.
      r - r value.
      fromIndex - initial value.