scalation.util

Sorting

class Sorting[T] extends AnyRef

The Sorting 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 generic.

See also

SortingD for a version of this class specialized for Doubles.

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By inheritance
Inherited
  1. Sorting
  2. AnyRef
  3. Any
  1. Hide All
  2. Show all
Learn more about member selection
Visibility
  1. Public
  2. All

Instance Constructors

  1. new Sorting(a: Array[T])(implicit arg0: (T) ⇒ Ordered[T])

    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): T

    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 iqsort(): Array[Int]

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

  13. final def isInstanceOf[T0]: Boolean

    Definition Classes
    Any
  14. def isSorted(rk: Array[Int]): Boolean

    Determine whether the array 'a' is indirectly sorted.

    Determine whether the array 'a' is indirectly sorted.

    rk

    the rank order

  15. def isSorted: Boolean

    Determine whether the array 'a' is sorted.

  16. def iselsort(): Array[Int]

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

  17. def median(rk: Array[Int], p: Int, r: Int, k: Int): T

    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

  18. def median(k: Int = (n+1)/2): T

    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)

  19. def median(p: Int, r: Int, k: Int): T

    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

  20. final def ne(arg0: AnyRef): Boolean

    Definition Classes
    AnyRef
  21. final def notify(): Unit

    Definition Classes
    AnyRef
  22. final def notifyAll(): Unit

    Definition Classes
    AnyRef
  23. def partition(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

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

  25. def qsort(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

  26. def qsort(): Unit

    Sort array 'a' using QuickSort.

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

  28. def selsort(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

  29. def selsort(): Unit

    Sort array 'a' using SelectionSort.

  30. def selsort(p: Int, r: Int): 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

  31. final def synchronized[T0](arg0: ⇒ T0): T0

    Definition Classes
    AnyRef
  32. def toString(): String

    Definition Classes
    AnyRef → Any
  33. final def wait(): Unit

    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  34. final def wait(arg0: Long, arg1: Int): Unit

    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  35. final def wait(arg0: Long): Unit

    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Inherited from AnyRef

Inherited from Any

Ungrouped