“This is the 24th day of my participation in the August More Text Challenge.

The concept of quicksort

The quicksort implementation is simple to use for a wide variety of input data and is much faster than other sorting algorithms in general applications. The interesting features of quicksort include that it sorts in place (requiring only a small auxiliary stack) and that the time it takes to sort an array of length N is proportional to NlgN.

Quicksort also has a shorter inner loop than most sorting algorithms, which means it is faster in theory and practice.

Its main disadvantage is that it is very fragile and has to be implemented with great care to avoid poor performance.

Second, the basic algorithm

Quicksort is a divide-and-conquer sorting algorithm. It splits an array into two subarrays, sorting the two parts independently.

Quicksort and merge sort are complementary: merge sort divides an array into two subarrays and sorts them separately, and merges the ordered subarrays to sort the entire array; Quicksort sorts an array in such a way that when both subarrays are ordered the entire array is ordered

In the first case, the recursive call occurs before processing the entire array; In the second case, the recursive call occurs after processing the entire array. In merge sort, an array is equally divided in half; In quicksort, the location of the shard depends on the contents of the array.

Three, code implementation

Quicksort:

public class Quick {

    public static void sort(Comparable[] arr) {

        // Shuffle the array order
        Random rand = new Random(47);
        List list = Arrays.asList(arr);
        Collections.shuffle(list, rand);
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(Comparable[] arr, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int j = partition(arr, lo, hi);
        sort(arr, lo, j - 1);
        sort(arr, j + 1, hi);
    }

    private static int partition(Comparable[] arr, int lo, int hi) {
        // Divide array into arr[lo...i-1],a[I],a[I +1...hi]
        // Scan pointer left and right
        int i = lo, j = hi + 1;
        // Shards elements
        Comparable v = arr[lo];
        while (true) {
            while (SortUtil.less(arr[++i], v)) {
                if (i == hi) {
                    break; }}while (SortUtil.less(v, arr[--j])) {
                if (j == lo) {
                    break; }}if (i >= j) {
                break;
            }
        }
        SortUtil.exch(arr, lo, j);
        returnj; }}Copy the code

Tools:

public class SortUtil {

    // Compare elements
    public static boolean less(Comparable v, Comparable w) {
        // returns -1/0/1: indicates that v is less than/equal to/greater than w
        return v.compareTo(w) < 0;
    }

    // Swap elements
    public static void exch(Comparable[] arr, int i, int j) {
        Comparable t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Display the array
    public static void show(Comparable[] arr) {
        for (Comparable comparable : arr) {
            System.out.println(comparable + ""); }}// Check whether the array is in order
    public static boolean isSorted(Comparable[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (less(arr[i], arr[i - 1]) {return false; }}return true; }}Copy the code

Quicksort algorithm analysis

Quicksort recursively sorts the subarray A [lo… hi], using partition() to place a[j] in an appropriate position, and then recursively sorts the elements in other positions.

Citation from Algorithms (4th Edition)

The key to this method is shard, which makes arrays satisfy the following three conditions:

1, for a certain J, a[j] and scheduling

2. All elements in a[LO] to A [J-1] are not larger than A [J].

3. All elements in a[j+1] to A [hi] are not less than A [J].

Sort by recursively calling shard. Since shard always arranges an element, it’s not hard to prove recursion will sort the array correctly using induction: If both the left and right subarrays are ordered, then a structured array consisting of the left subarray (ordered and no element larger than the shard element), the shard element, and the right subarray (ordered and no element smaller than the shard element) must also be ordered.

To complete this implementation, you need to implement the shard method. After randomly shuffling the array, take a[LO] as the shard element, then scan from the left end of the array to the right until it finds a primitive greater than or equal to it, and from the right end of the array to the left until it finds an element less than or equal to it. These two elements are obviously not scheduled, so we switch their positions. If we continue this way, we guarantee that no element to the left of the left pointer is greater than the shard element, and no element to the right of the right pointer J is less than the shard element. When two Pointers meet, simply swap the shard element A [lo] with the right-most element of the left subarray (a[j]) and return j.

Basic properties of quicksort algorithm

1. To sort a non-repeating array of length N, quicksort takes ~2NlnN comparisons (and 1/6 swaps) on average.

2. Quicksort requires at most about N^2/2 comparisons, but randomly shuffling the array prevents this.