Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

preface

This is the fifth and final installment in the Elegant series.

1. How to gracefully implement binary search

2. How to implement bubble sort elegantly

3. Elegant implementation of selection sorting

4. How to implement insert sort elegantly

Today we are going to take a look at quicksort, I feel this is the most difficult one in the elegant series, everyone ready to go!

Algorithm description

  1. We start by setting a boundary that divides the array into left and right parts.
  2. Centralize data greater than or equal to the boundary to the right of the array, and data less than the boundary to the left of the array. At this point, each element in the left part is less than or equal to the boundary value, and each element in the right part is greater than or equal to the boundary value.
  3. Then, the data on the left and right can be sorted independently. For the left side of the array, you can take a boundary value and divide that part of the data into left and right parts, again placing a smaller value on the left and a larger value on the right. The array data on the right can be treated similarly.
  4. Repeat the above process, and you can see that this is a recursive definition. After recursively ordering the left side, recursively ordering the right side. When the sorting of the left and right parts of the data is complete, the sorting of the entire array is complete.

I don’t know what you think of the above description, but in fact, it reflects the idea of divide and conquer, divide and compare. So this is the one element that we need, and the time that we have to evaluate it so many times that it can’t be divided, is when we get an ordered array.

Quicksort can be implemented in a variety of ways, and I’m going to offer two.

Lomuto zoning scheme

Lomuto partitioning is also known as unilateral loop quicksort. The concrete implementation is as follows:

  1. Select the rightmost element as the reference element
  2. The I pin maintains the boundary of elements less than the reference point and is the target index for each exchange
  3. J is responsible for finding elements smaller than the reference point, and once found, it swaps with I
  4. The final datum is swapped with I, which is the partition location

Single side loop implementation

private static void quick(int[] a, int low, int high){
    if(low >= high) {
        return;
    }
    int p = partition(a, low, high);
    quick(a, low, p - 1);
    quick(a, p + 1, high);
}

// Find the position of the reference point and return
private static int partition(int[] a, int low, int high) {
    int pv = a[high]; // Reference point, here is the setting of omuto zoning scheme
    int i = low;
    for(int j = low; j < high; j ++) {
        if(a[j] < pv) {
            swap(a, i, j);
            i ++;
        }
    }
    swap(a, i, high);
    return i;
}

private static void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}
Copy the code

Quick is a recursive call to the left and right of a reference point. Low >= high indicates that all elements have been traversed.

Realization two: bilateral circulation fast row

  1. Choose the leftmost element as the reference element
  2. The j pointer is responsible for looking for elements smaller than the reference point from right to left, and the I pointer is responsible for looking for elements larger than the reference point from left to right. Once the two are found, they are swapped until I and J intersect
  3. The FINAL datum is swapped with I (where I and J are equal), and I is the partition location
private static void quick(int[] a, int low, int high){
    if(low >= high) {
        return;
    }
    int p = partition(a, low, high);
    quick(a, low, p - 1);
    quick(a, p + 1, high);
}

// Find the position of the reference point and return
private static int partition(int[] a, int low, int high) {
    int pv = a[low],  i = low, j = high;
    while(i < j){
        // j search from right to left
        while(i < j && a[j] > pv) {
            j --;
        }

        while(i < j && a[i] <= pv) {
            i ++;
        }

        // Separate the sizes
        swap(a, i, j);
    }

    // Permutation of the datum element
    swap(a, low, i);
    return i;
}

private static void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}
Copy the code

While (I < j &&a [I] <= pv) while(I < j &&a [I] <= pv) while(I < j &&a [I] <= pv) I is also on the left hand side. It will overlap.

Quicksort features

Bubble sort is used to optimize bubble sort, bubble sort can only get one element at a time, whereas quicksort can get one element (reference point) on the first one, two elements on the second one, four elements on the third one, so if the array is very long, the efficiency improvement is very significant. One other thing, quicksort is unstable sort.

The last

This is the last article in the elegant series. I hope you can give us more likes and comments. We can communicate with each other and get a more elegant solution.