Package org.drip.graph.selection

Class HashSelector

java.lang.Object
org.drip.graph.selection.OrderStatisticSelector<java.lang.Double>
org.drip.graph.selection.HashSelector
public class HashSelector
extends OrderStatisticSelector<java.lang.Double>
HashSelector implements the Hash-table Based Selection Algorithm. The References are:

  • Eppstein, D. (2007): Blum-style Analysis of Quickselect https://11011110.github.io/blog/2007/10/09/blum-style-analysis-of.html
  • Hoare, C. A. R. (1961): Algorithm 65: Find Communications of the ACM 4 (1) 321-322
  • Knuth, D. (1997): The Art of Computer Programming 3rd Edition Addison-Wesley
  • Wikipedia (2019): Quickselect https://en.wikipedia.org/wiki/Quickselect
  • Wikipedia (2019): Selection Algorithm https://en.wikipedia.org/wiki/Selection_algorithm




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    HashSelector​(java.lang.Double[] elementArray, int bucketCount)
    HashSelector Constructor

  • Method Summary

    Modifier and Type Method Description
    int bucketCount()
    Retrieve the Count of Buckets
    static HashSelector FrequencyTable​(int[] integerArray)
    Construct a Frequency Table
    java.lang.Double select​(int k)
    Perform a Selection for the kth Order Statistic on the Array

    Methods inherited from class org.drip.graph.selection.OrderStatisticSelector

    elementArray, inPlace, sort

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • HashSelector

      public HashSelector​(java.lang.Double[] elementArray, int bucketCount) throws java.lang.Exception
      HashSelector Constructor
      Parameters:
      elementArray - Array of Elements
      bucketCount - Count of the Number of Buckets
      Throws:
      java.lang.Exception - Thrown if the Input is Invalid

  • Method Details

    • FrequencyTable

      public static final HashSelector FrequencyTable​(int[] integerArray)
      Construct a Frequency Table
      Parameters:
      integerArray - The Input Integer Array
      Returns:
      The Frequency Table

    • bucketCount

      public int bucketCount()
      Retrieve the Count of Buckets
      Returns:
      The Bucket Count

    • select

      public java.lang.Double select​(int k)
      Description copied from class: OrderStatisticSelector
      Perform a Selection for the kth Order Statistic on the Array
      Specified by:
      select in class OrderStatisticSelector<java.lang.Double>
      Parameters:
      k - The Order Statistic
      Returns:
      The kth Order Statistic