This is the third day of my participation in the August Text Challenge.More challenges in August

Quick sort

Preface:

Quicksort is a special sorting method compared with the previous sorting method

Principle:

1. Select an pivot element from the sequence (pivot). Assume that the pivot element at position 0 is selected each time.

2. Use Pivot to split the sequence into 2 sub-sequences. Place the element smaller than Pivot in front of pivot (left) and the element larger than pivot behind pivot (right) on either side

3. Perform 1, 2 operations on the subsequence until it can no longer be split (there is only 1 element left in the subsequence)

The essence of quicksort: gradually convert each element to an axis point element

Quicksort – Axis point construction

Once we have one pivot point, we split the array into two parts, and we can construct a front pivot point, and a back pivot point; Similarly, when each element becomes a pivot point, the array arrangement is complete.

Example:

protected void sort() { sort(0, array.length); @param begin @param end private void sort(int begin, int end) Int end) {if (end-begin < 2) return; O(n) int mid = pivotIndex(begin, end); /** * pivotIndex(pivotIndex, pivotIndex, pivotIndex, pivotIndex, pivotIndex, pivotIndex, pivotIndex, pivotIndex, pivotIndex, pivotIndex); Int end) {// Select a random element to swap with begin. Begin + (int)(math.random () * (end-begin))); // Pivot = array[begin]; // This is an amazing alternating loop, While (begin < end) {while (begin < end) {if (CMP (pivot, Array [end]) < 0) {begin <= array[begin++] = array[end]; break;}} while (begin < begin)  end) { if (cmp(pivot, Array [begin]) > 0) {// Begin ++;} else {// Left element >= Array [end--] = array[begin]; break;}}} // Array [begin] = pivot; return begin;}Copy the code

Algorithm analysis:

Quicksort – elements equal to axis points

If all elements in the sequence are equal to the axis-point elements, the axis-point elements can split the sequence into 2 uniform sub-sequences using the current algorithm implementation

We implemented the else in if else if the other elements are equal to the axis point, but what if we changed ‘<‘ or ‘>’ to ‘<=’ or ‘>=’?

As a result, it is obvious that it causes extremely uneven sub-sequences of the axis elements cut out, which affects efficiency and leads to the worst time complexity.

Hill sorting

Preface:

It always feels like hill sort is like merge, but! It works just like insertion sort, with fewer and fewer inversions

Principle:

Hill sort treats a sequence as a matrix, divided into 𝑚 columns, sorted column by column

𝑚 diminishes from some integer to 1

When 𝑚 is 1, the entire sequence is completely ordered

Therefore, Hill Sort is also called Diminishing Increment Sort.

The number of columns of the matrix depends on the step sequence.

For example, if the step sequence is {1,5,19,41,109… }, the representatives are sorted into 109 columns, 41 columns, 19 columns, 5 columns and 1 column

The execution efficiency is also different for different step sequences

Hill himself gave the step sequence as 𝑛/2𝑘. For example, when 𝑛 is 16, the step sequence is {1, 2, 4, 8}.

Sort into eight columns

Sort into four columns

Sort by 2 columns

Sort by 1 column

It’s not hard to see, the number of inversions decreases as you go from 8 columns to 1 column; Therefore, the bottom of Hill sort generally uses insert sort to sort each column, and many data think hill sort is an improved version of insert sort

Example:

Protected void sort() {List<Integer> stepSequence = sedgewickStepSequence(); For (Integer step: stepSequence) {sort(step); Private void sort(int step) {private void sort(int step) {// col: for (int col = 0; col < step; Col ++) {// col, col+step, col+2*step, col+3*step for (int begin = col+step; begin < array.length; begin += step) { int cur = begin; while (cur > col && cmp(cur, cur - step) < 0) { swap(cur, cur - step); cur -= step; }}}} // Private List<Integer> shellStepSequence() {List<Integer> stepSequence = new ArrayList<>(); int step = array.length; while ((step >>= 1) > 0) { stepSequence.add(step); } return stepSequence; } private List<Integer> sedgewickStepSequence() {List<Integer> stepSequence = new LinkedList<>(); int k = 0, step = 0; while (true) { if (k % 2 == 0) { int pow = (int) Math.pow(2, k >> 1); step = 1 + 9 * (pow * pow - pow); } else { int pow1 = (int) Math.pow(2, (k - 1) >> 1); int pow2 = (int) Math.pow(2, (k + 1) >> 1); step = 1 + 8 * pow1 * pow2 - 6 * pow2; } if (step >= array.length) break; stepSequence.add(0, step); k++; } return stepSequence; }Copy the code

Hill sort – step size sequence

Perhaps the most soulful aspect of Hill sorting is the step size sequence

Hill sorting is to use the step sequence to divide the original sequence, and each division will affect the complexity of sorting, and the best known step sequence, the worst case time complexity is O(N4/3), proposed by Robert Sedgewick in 1986

Example:

private List<Integer> sedgewickStepSequence() {
        List<Integer> stepSequence = new LinkedList<>();
        int k = 0, step = 0;
        while (true) {
            if (k % 2 == 0) {
                int pow = (int) Math.pow(2, k >> 1);
                step = 1 + 9 * (pow * pow - pow);
            } else {
                int pow1 = (int) Math.pow(2, (k - 1) >> 1);
                int pow2 = (int) Math.pow(2, (k + 1) >> 1);
                step = 1 + 8 * pow1 * pow2 - 6 * pow2;
            }
            if (step >= array.length) break;
            stepSequence.add(0, step);
            k++;
        }
        return stepSequence;
    }
Copy the code