Class KthElement


  • public class KthElement
    extends java.lang.Object
    TODO
    • Constructor Summary

      Constructors 
      Constructor Description
      KthElement()  
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static void kthElement​(int k, byte[] values)
      Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int k, char[] values)
      Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int k, double[] values)
      Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int k, float[] values)
      Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int k, int[] values)
      Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int i, int j, int k, byte[] values)
      Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int i, int j, int k, char[] values)
      Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int i, int j, int k, double[] values)
      Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int i, int j, int k, float[] values)
      Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int i, int j, int k, int[] values)
      Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int i, int j, int k, long[] values)
      Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int i, int j, int k, short[] values)
      Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static <T extends java.lang.Comparable<T>>
      void
      kthElement​(int i, int j, int k, java.util.List<T> values)
      Partition a sublist of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static <T extends java.lang.Comparable<T>>
      void
      kthElement​(int i, int j, int k, java.util.List<T> values, int[] permutation)
      Partition a sublist of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static <T> void kthElement​(int i, int j, int k, java.util.List<T> values, int[] permutation, java.util.Comparator<? super T> comparator)
      Partition a sublist of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static <T> void kthElement​(int i, int j, int k, java.util.List<T> values, java.util.Comparator<? super T> comparator)
      Partition a sublist of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int k, long[] values)
      Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static void kthElement​(int k, short[] values)
      Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static <T extends java.lang.Comparable<T>>
      void
      kthElement​(int k, java.util.List<T> values)
      Partition a list of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static <T extends java.lang.Comparable<T>>
      void
      kthElement​(int k, java.util.List<T> values, int[] permutation)
      Partition a list of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static <T> void kthElement​(int k, java.util.List<T> values, int[] permutation, java.util.Comparator<? super T> comparator)
      Partition a list of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static <T> void kthElement​(int k, java.util.List<T> values, java.util.Comparator<? super T> comparator)
      Partition a list of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
      static <T extends java.lang.Comparable<T>>
      void
      kthElement​(java.util.ListIterator<T> i, java.util.ListIterator<T> j, int k)
      Partition a sublist such that the k-th smallest value is at position k, elements before the k-th are smaller or equal, and elements after the k-th are larger or equal.
      static <T extends java.lang.Comparable<T>>
      void
      kthElement​(java.util.ListIterator<T> i, java.util.ListIterator<T> j, int k, int[] permutation)
      Partition a sublist such that the k-th smallest value is at position k, elements before the k-th are smaller or equal, and elements after the k-th are larger or equal.
      static <T> void kthElement​(java.util.ListIterator<T> i, java.util.ListIterator<T> j, int k, int[] permutation, java.util.Comparator<? super T> comparator)
      Partition a sublist such that the k-th smallest value is at position k, elements before the k-th are smaller or equal, and elements after the k-th are larger or equal.
      static <T> void kthElement​(java.util.ListIterator<T> i, java.util.ListIterator<T> j, int k, java.util.Comparator<? super T> comparator)
      Partition a sublist such that the k-th smallest value is at position k, elements before the k-th are smaller or equal, and elements after the k-th are larger or equal.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • KthElement

        public KthElement()
    • Method Detail

      • kthElement

        public static void kthElement​(int i,
                                      int j,
                                      int k,
                                      byte[] values)
        Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
      • kthElement

        public static void kthElement​(int k,
                                      byte[] values)
        Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        k - index for k-th smallest value. 0 <= k < values.length.
        values - array
      • kthElement

        public static void kthElement​(int i,
                                      int j,
                                      int k,
                                      short[] values)
        Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
      • kthElement

        public static void kthElement​(int k,
                                      short[] values)
        Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        k - index for k-th smallest value. 0 <= k < values.length.
        values - array
      • kthElement

        public static void kthElement​(int i,
                                      int j,
                                      int k,
                                      int[] values)
        Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
      • kthElement

        public static void kthElement​(int k,
                                      int[] values)
        Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        k - index for k-th smallest value. 0 <= k < values.length.
        values - array
      • kthElement

        public static void kthElement​(int i,
                                      int j,
                                      int k,
                                      long[] values)
        Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
      • kthElement

        public static void kthElement​(int k,
                                      long[] values)
        Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        k - index for k-th smallest value. 0 <= k < values.length.
        values - array
      • kthElement

        public static void kthElement​(int i,
                                      int j,
                                      int k,
                                      float[] values)
        Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
      • kthElement

        public static void kthElement​(int k,
                                      float[] values)
        Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        k - index for k-th smallest value. 0 <= k < values.length.
        values - array
      • kthElement

        public static void kthElement​(int i,
                                      int j,
                                      int k,
                                      double[] values)
        Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
      • kthElement

        public static void kthElement​(int k,
                                      double[] values)
        Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        k - index for k-th smallest value. 0 <= k < values.length.
        values - array
      • kthElement

        public static void kthElement​(int i,
                                      int j,
                                      int k,
                                      char[] values)
        Partition a subarray of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
      • kthElement

        public static void kthElement​(int k,
                                      char[] values)
        Partition an array of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        k - index for k-th smallest value. 0 <= k < values.length.
        values - array
      • kthElement

        public static <T> void kthElement​(int i,
                                          int j,
                                          int k,
                                          java.util.List<T> values,
                                          java.util.Comparator<? super T> comparator)
        Partition a sublist of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
        comparator - ordering function on T
      • kthElement

        public static <T> void kthElement​(int k,
                                          java.util.List<T> values,
                                          java.util.Comparator<? super T> comparator)
        Partition a list of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        k - index for k-th smallest value. 0 <= k < values.size().
        values - array
        comparator - ordering function on T
      • kthElement

        public static <T extends java.lang.Comparable<T>> void kthElement​(int i,
                                                                          int j,
                                                                          int k,
                                                                          java.util.List<T> values)
        Partition a sublist of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
      • kthElement

        public static <T extends java.lang.Comparable<T>> void kthElement​(int k,
                                                                          java.util.List<T> values)
        Partition a list of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.
        Parameters:
        k - index for k-th smallest value. 0 <= k < values.size().
        values - array
      • kthElement

        public static <T> void kthElement​(java.util.ListIterator<T> i,
                                          java.util.ListIterator<T> j,
                                          int k,
                                          java.util.Comparator<? super T> comparator)
        Partition a sublist such that the k-th smallest value is at position k, elements before the k-th are smaller or equal, and elements after the k-th are larger or equal.

        After the function returns, the iterator i is on the k-th element. That is, i.next() gives the (k+1)-th element.

        Parameters:
        i - iterator pointing before first element of the sublist, that is, i.next() gives you the first element.
        j - iterator pointing behind the last element of the sublist, that is, i.previous() gives you the last element.
        k - index for k-th smallest value. i.nextIndex() <= k <= j.previousIndex().
        comparator - ordering function on T
      • kthElement

        public static <T extends java.lang.Comparable<T>> void kthElement​(java.util.ListIterator<T> i,
                                                                          java.util.ListIterator<T> j,
                                                                          int k)
        Partition a sublist such that the k-th smallest value is at position k, elements before the k-th are smaller or equal, and elements after the k-th are larger or equal.

        After the function returns, the iterator i is on the k-th element. That is, i.next() gives the (k+1)-th element.

        Parameters:
        i - iterator pointing before first element of the sublist, that is, i.next() gives you the first element.
        j - iterator pointing behind the last element of the sublist, that is, i.previous() gives you the last element.
        k - index for k-th smallest value. i.nextIndex() <= k <= j.previousIndex().
      • kthElement

        public static <T> void kthElement​(int i,
                                          int j,
                                          int k,
                                          java.util.List<T> values,
                                          int[] permutation,
                                          java.util.Comparator<? super T> comparator)
        Partition a sublist of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.

        The permutation array is permuted in the same way as the list. Usually, this will be an array of indices, so that the partition operation can be mirrored in another list: Suppose, we have a list of keys and a lists (or several) of values. If we use kthElement to sort the keys, we want to reorder the values in the same manner. We pass an indices array [0, 1, 2, ...] and use the permutation of the indices to permute the values list.

        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
        permutation - elements of this array are permuted in the same way as the elements in the values list
        comparator - ordering function on T
      • kthElement

        public static <T> void kthElement​(int k,
                                          java.util.List<T> values,
                                          int[] permutation,
                                          java.util.Comparator<? super T> comparator)
        Partition a list of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.

        The permutation array is permuted in the same way as the list. Usually, this will be an array of indices, so that the partition operation can be mirrored in another list: Suppose, we have a list of keys and a lists (or several) of values. If we use kthElement to sort the keys, we want to reorder the values in the same manner. We pass an indices array [0, 1, 2, ...] and use the permutation of the indices to permute the values list.

        Parameters:
        k - index for k-th smallest value. 0 <= k < values.size().
        values - array
        permutation - elements of this array are permuted in the same way as the elements in the values list
        comparator - ordering function on T
      • kthElement

        public static <T extends java.lang.Comparable<T>> void kthElement​(int i,
                                                                          int j,
                                                                          int k,
                                                                          java.util.List<T> values,
                                                                          int[] permutation)
        Partition a sublist of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.

        The permutation array is permuted in the same way as the list. Usually, this will be an array of indices, so that the partition operation can be mirrored in another list: Suppose, we have a list of keys and a lists (or several) of values. If we use kthElement to sort the keys, we want to reorder the values in the same manner. We pass an indices array [0, 1, 2, ...] and use the permutation of the indices to permute the values list.

        Parameters:
        i - index of first element of subarray
        j - index of last element of subarray
        k - index for k-th smallest value. i <= k <= j.
        values - array
        permutation - elements of this array are permuted in the same way as the elements in the values list
      • kthElement

        public static <T extends java.lang.Comparable<T>> void kthElement​(int k,
                                                                          java.util.List<T> values,
                                                                          int[] permutation)
        Partition a list of values such that the k-th smallest value is at position k, elements before the k-th are smaller or equal and elements after the k-th are larger or equal.

        The permutation array is permuted in the same way as the list. Usually, this will be an array of indices, so that the partition operation can be mirrored in another list: Suppose, we have a list of keys and a lists (or several) of values. If we use kthElement to sort the keys, we want to reorder the values in the same manner. We pass an indices array [0, 1, 2, ...] and use the permutation of the indices to permute the values list.

        Parameters:
        k - index for k-th smallest value. 0 <= k < values.size().
        values - array
        permutation - elements of this array are permuted in the same way as the elements in the values list
      • kthElement

        public static <T> void kthElement​(java.util.ListIterator<T> i,
                                          java.util.ListIterator<T> j,
                                          int k,
                                          int[] permutation,
                                          java.util.Comparator<? super T> comparator)
        Partition a sublist such that the k-th smallest value is at position k, elements before the k-th are smaller or equal, and elements after the k-th are larger or equal.

        After the function returns, the iterator i is on the k-th element. That is, i.next() gives the (k+1)-th element.

        The permutation array is permuted in the same way as the list. Usually, this will be an array of indices, so that the partition operation can be mirrored in another list: Suppose, we have a list of keys and a lists (or several) of values. If we use kthElement to sort the keys, we want to reorder the values in the same manner. We pass an indices array [0, 1, 2, ...] and use the permutation of the indices to permute the values list.

        Parameters:
        i - iterator pointing before first element of the sublist, that is, i.next() gives you the first element.
        j - iterator pointing behind the last element of the sublist, that is, i.previous() gives you the last element.
        k - index for k-th smallest value. i.nextIndex() <= k <= j.previousIndex().
        permutation - elements of this array are permuted in the same way as the elements in the values list
        comparator - ordering function on T
      • kthElement

        public static <T extends java.lang.Comparable<T>> void kthElement​(java.util.ListIterator<T> i,
                                                                          java.util.ListIterator<T> j,
                                                                          int k,
                                                                          int[] permutation)
        Partition a sublist such that the k-th smallest value is at position k, elements before the k-th are smaller or equal, and elements after the k-th are larger or equal.

        After the function returns, the iterator i is on the k-th element. That is, i.next() gives the (k+1)-th element.

        The permutation array is permuted in the same way as the list. Usually, this will be an array of indices, so that the partition operation can be mirrored in another list: Suppose, we have a list of keys and a lists (or several) of values. If we use kthElement to sort the keys, we want to reorder the values in the same manner. We pass an indices array [0, 1, 2, ...] and use the permutation of the indices to permute the values list.

        Parameters:
        i - iterator pointing before first element of the sublist, that is, i.next() gives you the first element.
        j - iterator pointing behind the last element of the sublist, that is, i.previous() gives you the last element.
        k - index for k-th smallest value. i.nextIndex() <= k <= j.previousIndex().
        permutation - elements of this array are permuted in the same way as the elements in the values list