Package smile.sort

Class QuickSort

java.lang.Object
smile.sort.QuickSort
public class QuickSort extends Object
Quicksort is a well-known sorting algorithm that, on average, makes O(n log n) comparisons to sort n items. For large n (say > 1000), Quicksort is faster, on most machines, by a factor of 1.5 or 2 than other O(n log n) algorithms. However, in the worst case, it makes O(n2) comparisons. Quicksort requires a bit of extra memory.

Quicksort is a comparison sort. A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator obey the three defining properties of a total order:

  • if a <= b and b <= a then a = b (antisymmetry)
  • if a <= b and b <= c then a <= c (transitivity)
  • a <= b or b <= a (totalness or trichotomy)

Quicksort, however, is not a stable sort in efficient implementations. Stable sorting algorithms maintain the relative order of records with equal keys. If all keys are different then this distinction is not necessary. But if there are equal keys, then a sorting algorithm is stable if whenever there are two records(let's say R and S) with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list.

For speed of execution, we implement it without recursion. Instead, we require an auxiliary array (stack) of storage, of length 2 log2 n. When a subarray has gotten down to size 7, we sort it by straight insertion.

  • Method Summary

    Modifier and Type
    Method
    Description
    static int[]
    sort(double[] x)
    Sorts the specified array into ascending numerical order.
    static void
    sort(double[] x, double[] y)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static void
    sort(double[] x, double[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static void
    sort(double[] x, int[] y)
    Besides sorting the array x, the array y will be also rearranged as the same order of x.
    static void
    sort(double[] x, int[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static void
    sort(double[] x, Object[] y)
    Besides sorting the array x, the array y will be also rearranged as the same order of x.
    static void
    sort(double[] x, Object[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static int[]
    sort(float[] x)
    Sorts the specified array into ascending numerical order.
    static void
    sort(float[] x, float[] y)
    Besides sorting the array x, the array y will be also rearranged as the same order of x.
    static void
    sort(float[] x, float[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static void
    sort(float[] x, int[] y)
    Besides sorting the array x, the array y will be also rearranged as the same order of x.
    static void
    sort(float[] x, int[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static void
    sort(float[] x, Object[] y)
    Besides sorting the array x, the array y will be also rearranged as the same order of x.
    static void
    sort(float[] x, Object[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static int[]
    sort(int[] x)
    Sorts the specified array into ascending numerical order.
    static void
    sort(int[] x, double[] y)
    Besides sorting the array x, the array y will be also rearranged as the same order of x.
    static void
    sort(int[] x, double[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static void
    sort(int[] x, int[] y)
    Besides sorting the array x, the array y will be also rearranged as the same order of x.
    static void
    sort(int[] x, int[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static void
    sort(int[] x, Object[] y)
    Besides sorting the array x, the array y will be also rearranged as the same order of x.
    static void
    sort(int[] x, Object[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static <T extends Comparable<? super T>>
    int[]
    sort(T[] x)
    Sorts the specified array into ascending order.
    static <T extends Comparable<? super T>>
    void
    sort(T[] x, int[] y)
    Besides sorting the array x, the array y will be also rearranged as the same order of x.
    static <T extends Comparable<? super T>>
    void
    sort(T[] x, int[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static <T> void
    sort(T[] x, int[] y, int n, Comparator<T> comparator)
    This is an efficient implementation Quick Sort algorithm without recursive.
    static <T extends Comparable<? super T>>
    void
    sort(T[] x, Object[] y)
    Besides sorting the array x, the array y will be also rearranged as the same order of x.
    static <T extends Comparable<? super T>>
    void
    sort(T[] x, Object[] y, int n)
    This is an efficient implementation Quick Sort algorithm without recursive.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • sort

      public static int[] sort(int[] x)
      Sorts the specified array into ascending numerical order.
      Parameters:
      x - the array.
      Returns:
      the original index of elements after sorting in range [0, n).

    • sort

      public static void sort(int[] x, int[] y)
      Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static void sort(int[] x, int[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.

    • sort

      public static void sort(int[] x, double[] y)
      Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static void sort(int[] x, double[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.

    • sort

      public static void sort(int[] x, Object[] y)
      Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static void sort(int[] x, Object[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.

    • sort

      public static int[] sort(float[] x)
      Sorts the specified array into ascending numerical order.
      Parameters:
      x - the array.
      Returns:
      the original index of elements after sorting in range [0, n).

    • sort

      public static void sort(float[] x, int[] y)
      Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static void sort(float[] x, int[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.

    • sort

      public static void sort(float[] x, float[] y)
      Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static void sort(float[] x, float[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.

    • sort

      public static void sort(float[] x, Object[] y)
      Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static void sort(float[] x, Object[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.

    • sort

      public static int[] sort(double[] x)
      Sorts the specified array into ascending numerical order.
      Parameters:
      x - the array to sort.
      Returns:
      the original index of elements after sorting in range [0, n).

    • sort

      public static void sort(double[] x, int[] y)
      Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static void sort(double[] x, int[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.

    • sort

      public static void sort(double[] x, double[] y)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static void sort(double[] x, double[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.

    • sort

      public static void sort(double[] x, Object[] y)
      Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static void sort(double[] x, Object[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.

    • sort

      public static <T extends Comparable<? super T>> int[] sort(T[] x)
      Sorts the specified array into ascending order.
      Type Parameters:
      T - the data type of array elements.
      Parameters:
      x - the array to sort.
      Returns:
      the original index of elements after sorting in range [0, n).

    • sort

      public static <T extends Comparable<? super T>> void sort(T[] x, int[] y)
      Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Type Parameters:
      T - the data type of array elements.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static <T extends Comparable<? super T>> void sort(T[] x, int[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Type Parameters:
      T - the data type of array elements.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.

    • sort

      public static <T> void sort(T[] x, int[] y, int n, Comparator<T> comparator)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Type Parameters:
      T - the data type of array elements.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.
      comparator - the comparator.

    • sort

      public static <T extends Comparable<? super T>> void sort(T[] x, Object[] y)
      Besides sorting the array x, the array y will be also rearranged as the same order of x.
      Type Parameters:
      T - the data type of array elements.
      Parameters:
      x - the array to sort.
      y - the associate array.

    • sort

      public static <T extends Comparable<? super T>> void sort(T[] x, Object[] y, int n)
      This is an efficient implementation Quick Sort algorithm without recursive. Besides sorting the first n elements of array x, the first n elements of array y will be also rearranged as the same order of x.
      Type Parameters:
      T - the data type of array elements.
      Parameters:
      x - the array to sort.
      y - the associate array.
      n - the first n elements to sort.