Package smile.sort

Class SortUtils


  • public class SortUtils
    extends java.lang.Object
    Some useful functions such as swap and swif-down used in many sorting algorithms.
    Author:
    Haifeng Li
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static void siftDown​(double[] arr, int k, int n)
      To restore the max-heap condition when a node's priority is decreased.
      static void siftDown​(float[] arr, int k, int n)
      To restore the max-heap condition when a node's priority is decreased.
      static void siftDown​(int[] arr, int k, int n)
      To restore the max-heap condition when a node's priority is decreased.
      static <T extends java.lang.Comparable<? super T>>
      void
      siftDown​(T[] arr, int k, int n)
      To restore the max-heap condition when a node's priority is decreased.
      static void siftUp​(double[] arr, int k)
      To restore the max-heap condition when a node's priority is increased.
      static void siftUp​(float[] arr, int k)
      To restore the max-heap condition when a node's priority is increased.
      static void siftUp​(int[] arr, int k)
      To restore the max-heap condition when a node's priority is increased.
      static <T extends java.lang.Comparable<? super T>>
      void
      siftUp​(T[] arr, int k)
      To restore the max-heap condition when a node's priority is increased.
      static void swap​(double[] arr, int i, int j)
      Swap two positions.
      static void swap​(float[] arr, int i, int j)
      Swap two positions.
      static void swap​(int[] arr, int i, int j)
      Swap two positions.
      static void swap​(java.lang.Object[] arr, int i, int j)
      Swap two positions.
      • Methods inherited from class java.lang.Object

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

      • swap

        public static void swap​(int[] arr,
                                int i,
                                int j)
        Swap two positions.
      • swap

        public static void swap​(float[] arr,
                                int i,
                                int j)
        Swap two positions.
      • swap

        public static void swap​(double[] arr,
                                int i,
                                int j)
        Swap two positions.
      • swap

        public static void swap​(java.lang.Object[] arr,
                                int i,
                                int j)
        Swap two positions.
      • siftUp

        public static void siftUp​(int[] arr,
                                  int k)
        To restore the max-heap condition when a node's priority is increased. We move up the heap, exchaning the node at position k with its parent (at postion k/2) if necessary, continuing as long as a[k/2] < a[k] or until we reach the top of the heap.
      • siftUp

        public static void siftUp​(float[] arr,
                                  int k)
        To restore the max-heap condition when a node's priority is increased. We move up the heap, exchaning the node at position k with its parent (at postion k/2) if necessary, continuing as long as a[k/2] < a[k] or until we reach the top of the heap.
      • siftUp

        public static void siftUp​(double[] arr,
                                  int k)
        To restore the max-heap condition when a node's priority is increased. We move up the heap, exchaning the node at position k with its parent (at postion k/2) if necessary, continuing as long as a[k/2] < a[k] or until we reach the top of the heap.
      • siftUp

        public static <T extends java.lang.Comparable<? super T>> void siftUp​(T[] arr,
                                                                              int k)
        To restore the max-heap condition when a node's priority is increased. We move up the heap, exchaning the node at position k with its parent (at postion k/2) if necessary, continuing as long as a[k/2] < a[k] or until we reach the top of the heap.
      • siftDown

        public static void siftDown​(int[] arr,
                                    int k,
                                    int n)
        To restore the max-heap condition when a node's priority is decreased. We move down the heap, exchanging the node at position k with the larger of that node's two children if necessary and stopping when the node at k is not smaller than either child or the bottom is reached. Note that if n is even and k is n/2, then the node at k has only one child -- this case must be treated properly.
      • siftDown

        public static void siftDown​(float[] arr,
                                    int k,
                                    int n)
        To restore the max-heap condition when a node's priority is decreased. We move down the heap, exchanging the node at position k with the larger of that node's two children if necessary and stopping when the node at k is not smaller than either child or the bottom is reached. Note that if n is even and k is n/2, then the node at k has only one child -- this case must be treated properly.
      • siftDown

        public static void siftDown​(double[] arr,
                                    int k,
                                    int n)
        To restore the max-heap condition when a node's priority is decreased. We move down the heap, exchanging the node at position k with the larger of that node's two children if necessary and stopping when the node at k is not smaller than either child or the bottom is reached. Note that if n is even and k is n/2, then the node at k has only one child -- this case must be treated properly.
      • siftDown

        public static <T extends java.lang.Comparable<? super T>> void siftDown​(T[] arr,
                                                                                int k,
                                                                                int n)
        To restore the max-heap condition when a node's priority is decreased. We move down the heap, exchanging the node at position k with the larger of that node's two children if necessary and stopping when the node at k is not smaller than either child or the bottom is reached. Note that if n is even and k is n/2, then the node at k has only one child -- this case must be treated properly.