class SortingI extends AnyRef
The SortingI 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 Int.
- See also
Sortingfor a generic version of this class.
- Alphabetic
- By Inheritance
- SortingI
- AnyRef
- Any
- Hide All
- Show All
- Public
- All
Instance Constructors
-
new
SortingI(a: Array[Int])
- 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
- @native() @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
- Annotations
- @native()
-
def
hashCode(): Int
- Definition Classes
- AnyRef → Any
- Annotations
- @native()
-
def
imedian(k: Int = (n+1)/2): Int
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
imedian(rk: Array[Int], p: Int, r: Int, k: Int): Int
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
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
-
def
iqsort(): Array[Int]
Indirectly sort array 'a' using
QuickSort, returning the rank order. -
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
-
def
iqsort2(): Array[Int]
Indirectly sort array 'a' using
QuickSort.Indirectly sort array 'a' using
QuickSort. Sort in decreasing order. -
final
def
isInstanceOf[T0]: Boolean
- Definition Classes
- Any
-
def
isSorted: Boolean
Determine whether the array 'a' is sorted in ascending order.
-
def
isSorted2: Boolean
Determine whether the array 'a' is sorted in descending order.
-
def
iselsort(): Array[Int]
Indirectly sort array 'a' using
SelectionSort, returning the rank order. -
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
-
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. -
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
-
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
-
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
-
def
median(k: Int = (n+1)/2): Int
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): Int
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
- Annotations
- @native()
-
final
def
notifyAll(): Unit
- Definition Classes
- AnyRef
- Annotations
- @native()
-
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
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
-
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
qsort2(): Unit
Sort array 'a' using
QuickSort.Sort array 'a' using
QuickSort. Sort in decreasing order. -
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
-
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
-
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
-
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
- @native() @throws( ... )