Packages

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 large arrays using MergeSort (slower than quicksort, but stable) 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

SortingC for a version of this class specialized for Complex.

SortingD for a version of this class specialized for Double.

SortingI for a version of this class specialized for Int.

SortingL for a version of this class specialized for Long.

SortingQ for a version of this class specialized for Rational.

SortingR for a version of this class specialized for Real.

SortingS for a version of this class specialized for StrNum.

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

Instance Constructors

  1. new Sorting(a: Array[T])(implicit arg0: (T) ⇒ Ordered[T], arg1: ClassTag[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[lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native() @HotSpotIntrinsicCandidate()
  6. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  7. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  8. final def getClass(): Class[_]
    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): 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)

  11. def iqsort(): Array[Int]

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

  12. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  13. 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

  14. def isSorted: Boolean

    Determine whether the array 'a' is sorted.

  15. def iselsort(k: Int, asc: Boolean = true): Array[Int]

    Partially, indirectly sort array 'a' using SelectionSort returning the first/smallest 'k' elements.

    Partially, indirectly sort array 'a' using SelectionSort returning the first/smallest 'k' elements. Can be used for top-k (smallest) or bottom-k (largest) selection.

    k

    the number of elements to sort and return

    asc

    whether to sort in ascending (true) or descending (false) order

  16. def iselsort(): Array[Int]

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

  17. final def med3(i: Int, j: Int, k: Int): Int

    Return the index of the median of three elements.

    Return the index of the median of three elements.

    i

    element index 1

    j

    element index 2

    k

    element index 3

    Annotations
    @inline()
    See also

    Sorting companion object for 'median3' function

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

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

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

    en.wikipedia.org/wiki/Quickselect

  21. def merge(x: Array[T], ii: Int, jj: Int, kk: Int, y: Array[T]): Unit

    Merge sorted runs of one array into another.

    Merge sorted runs of one array into another. Examaple: merge | 1, 3 | with | 2, 4 | to get | 1, 2, 3, 4 |. Run 1: x(ii until jj) Run 2: x(jj until kk)

    x

    the source (from) array

    ii

    the start of first run

    jj

    the start of second run

    kk

    the end (exclusive) of second run

    y

    the destination (to) array

  22. def msort(): Unit

    Sort array 'a' using MergeSort (stable sorting algorithm).

    Sort array 'a' using MergeSort (stable sorting algorithm). Uses a bottom-up approach.

    See also

    https://en.wikipedia.org/wiki/Merge_sort

  23. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  24. final def notify(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  25. final def notifyAll(): Unit
    Definition Classes
    AnyRef
    Annotations
    @native() @HotSpotIntrinsicCandidate()
  26. 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

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

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

  29. def qsort(): Unit

    Sort array 'a' using QuickSort (unstable sorting algorithm).

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

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

  32. def selsort(k: Int, asc: Boolean = true): Array[T]

    Partially sort array 'a' using SelectionSort returning the first/smallest 'k' elements.

    Partially sort array 'a' using SelectionSort returning the first/smallest 'k' elements. Can be used for top-k (smallest) or bottom-k (largest) selection.

    k

    the number of elements to sort and return

    asc

    whether to sort in ascending (true) or descending (false) order

  33. def selsort(): Unit

    Sort array 'a' using SelectionSort.

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

  35. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  36. def toString(): String
    Definition Classes
    AnyRef → Any
  37. def top(k: Int): Array[T]

    Return the smallest 'k' elements (top-k) of array 'a'.

    Return the smallest 'k' elements (top-k) of array 'a'.

    k

    the number of samllest elements to return

  38. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  39. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... ) @native()
  40. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

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