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. All

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[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  6. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  7. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  8. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  9. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
  10. def hashCode(): Int
    Definition Classes
    AnyRef → Any
  11. 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)

  12. 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

  13. 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

  14. def iqsort(): Array[Int]

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

  15. 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

  16. def iqsort2(): Array[Int]

    Indirectly sort array 'a' using QuickSort.

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

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

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

  19. def isSorted2: Boolean

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

  20. def iselsort(): Array[Int]

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

  21. 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

  22. 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.

  23. 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

  24. 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

  25. 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

  26. 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)

  27. 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

  28. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  29. final def notify(): Unit
    Definition Classes
    AnyRef
  30. final def notifyAll(): Unit
    Definition Classes
    AnyRef
  31. 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

  32. 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

  33. def qsort(): Unit

    Sort array 'a' using QuickSort.

  34. 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

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

  35. def qsort2(): Unit

    Sort array 'a' using QuickSort.

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

  36. 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

  37. 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

  38. 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

  39. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  40. def toString(): String
    Definition Classes
    AnyRef → Any
  41. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  42. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  43. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Inherited from AnyRef

Inherited from Any

Ungrouped