Quick sort

So first you pick a pivot, and then you go through the array,

  • I’m going to move everything less than pivot to the left of pivot,
  • Move everything greater than pivot to the right of pivot.

So the pivot position is set, that is, 1 element is placed.

Then sort the number to the left of the pivot 👈 and the number to the right of the pivot 👉, and you are done.

How about left and right?

Answer: Same method.

So quicksort also uses the idea of divide and conquer.

“Points”

Pick a pivot, and you divide the problem

  • On the left side of the pivot
  • The pivot on the right

These two questions.

“Cure”

The method described at the beginning, until there are no elements in each interval or only one element can be returned.

“Close”

Put it all together.

But how do you choose this pivot?

Take the middle one?

Take the first one?

Take the last one?

For example: {5, 2, 1, 0, 3}.

Let’s say I pick the last one, which is 3.

Then we need to divide the numbers other than 3 into “greater than 3” and “less than 3” parts, a process called partition.

We’re still using the idea of baffles here, so instead of actually having two arrays to store these two pieces, we’re going to have two baffles to partition the interval.

We use “two Pointers” (i.e., baffles) to divide the array into “three intervals”, so

  • The left-hand range is for elements smaller than Pivot;
  • The region on the right is used to magnify the pivot element;
  • In the middle is the unsorted interval.

So when we initialize, we want to make sure that the unsorted interval contains everything except 3, so

  • Unordered interval = [I, j]

So the interval between the left and right is:

  • [0, I) : put a number less than 3;
  • (j, array.length-2) : Put the number larger than 3

Notice ⚠️ I and j are not included in the left and right intervals.

So our goal is to check every item in the unsorted interval, and then group it into the correct interval, so that we can reduce the unsorted interval until there are no unsorted elements.

Check from left to right:

Step1.

5 > 3, so 5 has to be in the right interval, so 5 and j point to 0 swap:


So we have 5 sorted, j — so we have one less number in our unsorted interval;

Step2.

0 is less than 3, so it’s going to be on the left-hand side, i++;


Step3.

2 is less than 3, same thing, i++;


Step4.

1 is less than 3, same thing, i++;


So when two Pointers are out of place, we end the loop.

But we’re missing a step. The three is not in the right place. So I’m going to insert it between the two intervals, so I’m going to swap it with the pointer I.



Disclaimer: Putting Pivot on the far left is not encouraged.

Almost all books are placed on the right side, since the left side is the same, we follow the default, consensus, there is no need to “unconventional”.

It’s like the four star positions in go, but the best way to move is to fall on your own star position first, not to reach your opponent’s side with your arm outstretched.

When we switch the pivot back to the correct position, the partition ends.

And then I’ll just write it recursively, sort the left and right.

There are two final questions I’d like to discuss with you:

  1. Going back to our original pivot question, is it a good idea to take the last one every time?

A: Not good.

Because we want to split the array more evenly, so the time complexity of uniformity is lower; But if this is an ordered array, then always picking the last one is the least uniform way to pick it.

So you should pick pivot at random, so you don’t have to pick the highest value because of the nature of the array.

  1. The pivot on which

After a random selection, we still need to place the pivot at the far right of the entire array so that our unsorted interval is continuous, otherwise we will be tired of trying to skip it every time we go to pivot.

class Solution {

  public void quickSort(int[] array) {

    if (array == null || array.length <= 1) {

      return;

    }

    quickSort(array, 0, array.length - 1);

  }

  private void quickSort(int[] array, int left, int right) {

    // base case

    if (left >= right) {

      return;

    }



    // partition

    Random random = new Random(); // random number generator in java.util

    int pivotIndex = left + random.nextInt(right - left + 1);

    swap(array, pivotIndex, right);



    int i = left;

    int j = right-1;

    while (i <= j) {

      if (array[i] <= array[right]) {

        i++;

      } else {

        swap(array, i, j);

        j--;

      }

    }

    swap(array, i, right);



    / / "points"

    quickSort(array, left, i-1);

    quickSort(array, i+1, right);

  }

  private void swap(int[] array, int x, int y) {

    int tmp = array[x];

    array[x] = array[y];

    array[y] = tmp;

  }

}



Copy the code

The time and space complexity here has a great relationship with whether the distribution is even, so we divide it into cases:

1. Divide

Time complexity

If I split it pretty evenly every time, then

  • The time for each loop is mainly in this while loop, which is O(right-left);
  • If it’s evenly divided, that’s the Logn layer;
  • So the total time is order nlogn.

Spatial complexity

  • The height of the recursion tree is logn,
  • The space complexity of each layer is O(1),
  • So the total space complexity is order logn.

2. Most uneven

If the Max/min is picked every time, the recursion tree looks like this:


Time complexity

O(n^2)

Spatial complexity

The height of this recursion tree becomes order (n).

3. Summary

In fact, most cases are close to the uniform case, so the uniform case is an average case.

Why is it that what looks like the best case is actually an average case?

Because even if you didn’t get to the middle point, say, between 10% and 90%, you’d still have order n times per level, but you’d have log base nine, so the total time would still be order nlogn.

So the average time complexity of quicksort is O(nlogn).

The stability of

As you can see, during swap, the relative order between elements has been broken, so quicksort is not stable.

And that answers the question we asked at the beginning, which is

  • Why use quicksort for Primitive Type,

    • Because it’s the fastest;

  • Why merge with Object,

    • Because it’s stable and fast.

The above is all the content of the quick row, but also very often test the content of oh! In the next article, I will talk about a few topics derived from the quick list. Guess what? 😉

If you like this article, please give me a thumbs up and leave a comment. Your support and recognition are the biggest motivation for my creation. See you in the next article!

I’m Xiao Qi, New York programming girl, lifelong learner, every night at 9 o ‘clock in the cloud study room!

More dry article see my lot: https://github.com/xiaoqi6666/NYCSDE