Packages

class SortingQ extends AnyRef

The SortingQ class provides direct and indirect methods to:

find 'k'-th median ('k'-th smallest element) using QuickSelect sort large arrays using QuickSort sort small arrays using SelectionSort

Direct methods are faster, but modify the array, while indirect methods are slower, but do not modify the array. This class is specialized for Rational.

See also

Sorting for a generic version of this class.

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. SortingQ
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. Protected

Instance Constructors

  1. new SortingQ(a: Array[Rational])

    a

    the array to operate on

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##: Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def clone(): AnyRef
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.CloneNotSupportedException]) @native() @HotSpotIntrinsicCandidate()
  6. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  7. def equals(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef → Any
  8. final def getClass(): Class[_ <: AnyRef]
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  9. def hashCode(): Int
    Definition Classes
    AnyRef → Any
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  10. def imedian(k: Int = (n+1)/2): Rational

    Indirectly find the 'k'-median ('k'-th smallest element) of array 'a'.

    Indirectly find the 'k'-median ('k'-th smallest element) of array 'a'.

    k

    the type of median (e.g., k = (n+1)/2 is the median)

  11. def imedian(rk: Array[Int], p: Int, r: Int, k: Int): Rational

    Indirectly find the 'k'-median of the 'p' to 'r' partition of array 'a' using the QuickSelect algorithm.

    Indirectly find the 'k'-median of the 'p' to 'r' partition of array 'a' using the QuickSelect algorithm.

    rk

    the rank order

    p

    the left cursor

    r

    the right cursor

    k

    the type of median (k-th smallest element)

    See also

    http://en.wikipedia.org/wiki/Quickselect

  12. def ipartition(rk: Array[Int], p: Int, r: Int): Int

    Indirectly partition the array from 'p' to 'r' into a left partition (<= 'x') and a right partition (>= 'x').

    Indirectly partition the array from 'p' to 'r' into a left partition (<= 'x') and a right partition (>= 'x').

    rk

    the rank order

    p

    the left cursor

    r

    the right cursor

  13. def iqsort(): Array[Int]

    Indirectly sort array 'a' using QuickSort, returning the rank order.

  14. def iqsort(rk: Array[Int], p: Int, r: Int): Unit

    Recursively and indirectly sort the 'p' to 'r' partition of array 'a' using QuickSort.

    Recursively and indirectly sort the 'p' to 'r' partition of array 'a' using QuickSort.

    rk

    the rank order

    p

    the left cursor

    r

    the right cursor

  15. def iqsort2(): Array[Int]

    Indirectly sort array 'a' using QuickSort.

    Indirectly sort array 'a' using QuickSort. Sort in decreasing order.

  16. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  17. def isSorted: Boolean

    Determine whether the array 'a' is sorted in ascending order.

  18. def isSorted2: Boolean

    Determine whether the array 'a' is sorted in descending order.

  19. def iselsort(): Array[Int]

    Indirectly sort array 'a' using SelectionSort, returning the rank order.

  20. def iselsort(rk: Array[Int], p: Int, r: Int): Unit

    Indirectly sort the 'p' to 'r' partition of array 'a' using SelectionSort.

    Indirectly sort the 'p' to 'r' partition of array 'a' using SelectionSort.

    rk

    the rank order

    p

    the left cursor

    r

    the right cursor

  21. def iselsort2(): Array[Int]

    Indirectly sort array 'a' using SelectionSort, returning the rank order.

    Indirectly sort array 'a' using SelectionSort, returning the rank order. Sort in decreasing order.

  22. def iselsort2(rk: Array[Int], p: Int, r: Int): Unit

    Indirectly sort the 'p' to 'r' partition of array 'a' using SelectionSort.

    Indirectly sort the 'p' to 'r' partition of array 'a' using SelectionSort. Sort in decreasing order.

    rk

    the rank order

    p

    the left cursor

    r

    the right cursor

  23. def isiSorted(rk: Array[Int]): Boolean

    Determine whether the array 'a' is indirectly sorted in ascending order.

    Determine whether the array 'a' is indirectly sorted in ascending order.

    rk

    the rank order

  24. def isiSorted2(rk: Array[Int]): Boolean

    Determine whether the array 'a' is indirectly sorted in ascending order.

    Determine whether the array 'a' is indirectly sorted in ascending order.

    rk

    the rank order

  25. def median(k: Int = (n+1)/2): Rational

    Find the 'k'-median ('k'-th smallest element) of array 'a'.

    Find the 'k'-median ('k'-th smallest element) of array 'a'.

    k

    the type of median (e.g., k = (n+1)/2 is the median)

  26. def median(p: Int, r: Int, k: Int): Rational

    Find the 'k'-median of the 'p' to 'r' partition of array 'a' using the QuickSelect algorithm.

    Find the 'k'-median of the 'p' to 'r' partition of array 'a' using the QuickSelect algorithm.

    p

    the left cursor

    r

    the right cursor

    k

    the type of median (k-th smallest element)

    See also

    http://en.wikipedia.org/wiki/Quickselect

  27. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  28. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  29. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  30. def partition(p: Int, r: Int): Int

    Partition the array from 'p' to 'q' into a left partition (<= 'x') and a right partition (>= 'x').

    Partition the array from 'p' to 'q' into a left partition (<= 'x') and a right partition (>= 'x').

    p

    the left cursor

  31. def partition2(p: Int, r: Int): Int

    Partition the array from 'p' to 'q' into a left partition (<= 'x') and a right partition (>= 'x').

    Partition the array from 'p' to 'q' into a left partition (<= 'x') and a right partition (>= 'x'). For sorting in decreasing order.

    p

    the left cursor

  32. def qsort(): Unit

    Sort array 'a' using QuickSort.

  33. def qsort(p: Int, r: Int): Unit

    Recursively sort the 'p' to 'r' partition of array 'a' using QuickSort.

    Recursively sort the 'p' to 'r' partition of array 'a' using QuickSort.

    p

    the left cursor

    r

    the right cursor

    See also

    mitpress.mit.edu/books/introduction-algorithms

  34. def qsort2(): Unit

    Sort array 'a' using QuickSort.

    Sort array 'a' using QuickSort. Sort in decreasing order.

  35. def qsort2(p: Int, r: Int): Unit

    Recursively sort the 'p' to 'r' partition of array 'a' using QuickSort.

    Recursively sort the 'p' to 'r' partition of array 'a' using QuickSort. Sort in decreasing order.

    p

    the left cursor

    r

    the right cursor

    See also

    http://mitpress.mit.edu/books/introduction-algorithms

  36. def selsort(p: Int = 0, r: Int = n-1): Unit

    Sort the 'p' to 'r' partition of array 'a' using SelectionSort.

    Sort the 'p' to 'r' partition of array 'a' using SelectionSort.

    p

    the left cursor

    r

    the right cursor

  37. def selsort2(p: Int = 0, r: Int = n-1): Unit

    Sort the 'p' to 'r' partition of array 'a' using SelectionSort.

    Sort the 'p' to 'r' partition of array 'a' using SelectionSort. Sort in decreasing order.

    p

    the left cursor

    r

    the right cursor

  38. final def synchronized[T0](arg0: => T0): T0
    Definition Classes
    AnyRef
  39. def toString(): String
    Definition Classes
    AnyRef → Any
  40. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])
  41. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException]) @native()
  42. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.InterruptedException])

Deprecated Value Members

  1. def finalize(): Unit
    Attributes
    protected[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws(classOf[java.lang.Throwable]) @Deprecated
    Deprecated

Inherited from AnyRef

Inherited from Any

Ungrouped