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
SortingSfor a version of this class specialized forStrNum.SortingRfor a version of this class specialized forReal.SortingQfor a version of this class specialized forRational.SortingLfor a version of this class specialized forLong.SortingIfor a version of this class specialized forInt.SortingDfor a version of this class specialized forDouble.SortingCfor a version of this class specialized forComplex.
- Alphabetic
- By Inheritance
- Sorting
- AnyRef
- Any
- Hide All
- Show All
- Public
- All
Instance Constructors
-
new
Sorting(a: Array[T])(implicit arg0: (T) ⇒ Ordered[T])
- a
the array to operate on
Value Members
-
final
def
!=(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
final
def
##(): Int
- Definition Classes
- AnyRef → Any
-
final
def
==(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
final
def
asInstanceOf[T0]: T0
- Definition Classes
- Any
-
def
clone(): AnyRef
- Attributes
- protected[java.lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
eq(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
def
equals(arg0: Any): Boolean
- Definition Classes
- AnyRef → Any
-
def
finalize(): Unit
- Attributes
- protected[java.lang]
- Definition Classes
- AnyRef
- Annotations
- @throws( classOf[java.lang.Throwable] )
-
final
def
getClass(): Class[_]
- Definition Classes
- AnyRef → Any
-
def
hashCode(): Int
- Definition Classes
- AnyRef → Any
-
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)
-
def
iqsort(): Array[Int]
Indirectly sort array 'a' using
QuickSort, returning the rank order. -
final
def
isInstanceOf[T0]: Boolean
- Definition Classes
- Any
-
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
-
def
isSorted: Boolean
Determine whether the array 'a' is sorted.
-
def
iselsort(): Array[Int]
Indirectly sort array 'a' using
SelectionSort, returning the rank order. -
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
QuickSelectalgorithm.Indirectly find the 'k'-median of the 'p' to 'r' partition of array 'a' using the
QuickSelectalgorithm.- 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
-
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)
-
def
median(p: Int, r: Int, k: Int): T
Find the 'k'-median of the 'p' to 'r' partition of array 'a' using the
QuickSelectalgorithm.Find the 'k'-median of the 'p' to 'r' partition of array 'a' using the
QuickSelectalgorithm.- 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
-
final
def
ne(arg0: AnyRef): Boolean
- Definition Classes
- AnyRef
-
final
def
notify(): Unit
- Definition Classes
- AnyRef
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
-
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
-
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
-
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
-
def
qsort(): Unit
Sort array 'a' using
QuickSort. -
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
-
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
-
def
selsort(): Unit
Sort array 'a' using
SelectionSort. -
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
-
final
def
synchronized[T0](arg0: ⇒ T0): T0
- Definition Classes
- AnyRef
-
def
toString(): String
- Definition Classes
- AnyRef → Any
-
final
def
wait(): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long, arg1: Int): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )
-
final
def
wait(arg0: Long): Unit
- Definition Classes
- AnyRef
- Annotations
- @throws( ... )