Quick sort

We did merge sort, and we did merge sort, and we made it very inefficient 。

It uses the idea of divide and conquer, and it uses recursion in applying that idea, which leads us to the structure of a tree

In the tree structure, we find that this is very efficient.

Inspired by 1

There is a small detail here, one of the students must be quickly standing across from the teacher, and then we know whether we should be on the left or right of the teacher based on the height of the middleman.

And then when it’s on the left or on the right, we think about who the person on the left is and who the person on the right is, and then we make an accurate comparison.

But that assumes two things

  1. During the quick gathering, the middleman could immediately stand in front of the teacher, because the queue had been arranged before, and the middleman quickly stood in front of the teacher according to his memory.
  2. After the students except the middleman judged left and right, the subsequent adjustments were made by memory, such as who was on my left and who was on my right

Inspired by 2

Let’s review merge sort now

In the red box, we cut the array to the minimum size.

And then, in the blue box, merge the arrays.

What if I wanted to improve this sorting algorithm? What would you think?

Can we integrate the behavior of the blue box and the red box?

That is, when you cut it, the array is in order, and when you cut it, the array is in order, right?

Inspiration 1 + Inspiration 2

So can we combine the quick set of Inspiration 1 with the two-in-one idea of Inspiration 2?

For an array of

let arr = [11.3.13.4.15.6.17]
Copy the code

If we know the exact median is 11, we divide the numbers less than 11 into the left chunk, and the numbers greater than 11 into the right chunk

And then divide the blue and red blocks using the same median

The whole array is in order!

In the above segmentation, we pretend to know exactly who the median is.

So the question is, if we don’t sort, how can we possibly know what the middle value of the array is?

So we can take a step back, since we don’t know the exact median

If we take an arbitrary number, and we divide the entire array by the size of the number that is directly larger than the number that is smaller than the number, then the two halves are probably not equal.

Since it’s arbitrary, in order to have some sense of the middle value, let’s take the middle number in the position, such as 4 in the figure below

And then we take anything greater than 4 as the left-hand side.

Let’s take anything less than 4 as the right-hand side.

Then repeat the above action, to have been divided out of the small pieces to the class median value segmentation

For example, if you only have 4 and 3 on the left, and you take 4 in the middle, you put the 3 to the right of the 4, you swap them

The right middle value is 15, so [13,11,6] becomes the new child left block, and [15, 16] becomes the new child right block

If we split [13, 11, 6], we’ll see that the array is already sorted

Code implementation

The middle value is too long a name, so let’s call it pivot

let arr = [11.3.13.4.15.6.17]
let pivot = arr[Math.floor((0 + arr.length) / 2)]
console.log(pivot); / / 4
Copy the code

So now the question is, how do I get numbers less than 4 on the left and numbers greater than 4 on the right?

Here is a particularly important idea to introduce: the idea of garbage sorting: there is no garbage, only misplaced resources.

Talk nonsense of

The one to the left of pivot is going to be smaller than him

The one on pivot’s right is bigger than him

So if we see something bigger than Pivot on the left, we go to the right and find something smaller than pivot, and when we swap the two, we get O!

Since we’re looking at both sides, we need to use two variables to cache elements, in this case the subscripts.

// Start from the left
let i = 0
// Start from the right
let j = arr.length - 1
Copy the code

So obviously, x goes to the right, so i++

Y to the left, y minus —

Let’s ask x to find something greater than 4, and then let’s ask y to find something greater than 4, and then let’s switch

I’m going to stop if x is less than or equal to y

So if I switch, I’m going to keep looking for x and y, so X ++,y-, or ELSE I’m just pointing to the original number.

But life is always skinny. What if you can’t find one side?

For example, arR = [1, 3, 13, 4, 15, 6, 17]

First I keeps adding to find a number greater than 4, namely arr[2] : 13

So let’s keep subtracting j to find something less than 4, arr[1]:3

The arR [1] is already on the left. Is it necessary to swap?

Of course not!

So we’re going to do an if (I <= j) before we swap, and we’re going to swap if we find both sides

Why <=? Leave it behind

So what are we gonna do?

No, you don’t see the position I is pointing to, arr[3], which is 13

[1, 3] and [13,4,15,6,17]

Exactly where the two halves of the size split? That’s what we wanted in the first place!

function partition(arr, left, right) {
  const pivot = arr[Math.floor((left + right) / 2)]
  let i = left
  let j = right
  while (i <= j) {
    while (arr[i] < pivot) i++
    while (pivot < arr[j]) j--
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
      i++
      j--
    }
  }
}
let arr = [11.3.13.4.15.6.17]
partition(arr, 0, arr.length - 1)
console.log(arr);
// [4, 3, 13, 11, 15, 6, 17]
Copy the code

So let’s review, what does our function do?

I’m going to split the array into two parts, so I’m going to return I

The caller can do a good job of dividing the array into two parts

function quickSort(arr) {
  return quick(arr, 0, arr.length - 1)}function quick(arr, left, right) {
  if (arr.length > 1) {
    let index = partition(arr, left, right)
    if (left < index - 1) quick(arr, left, index - 1)
    if (index < right) quick(arr, index, right)
  }
  return arr
}

function partition(arr, left, right) {
  let pivot = arr[Math.floor((left + right) / 2)]
  let i = left
  let j = right
  while (i <= j) {
    while (arr[i] < pivot) i++
    while (pivot < arr[j]) j--
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
      i++
      j--
    }
  }
  return i
}
Copy the code

So quicksort is done.

function quick(arr, left, right) {
  if (arr.length > 1) {
    let index = partition(arr, left, right)
    if (left < index - 1) quick(arr, left, index - 1)
    if (index < right) quick(arr, index, right)
  }
  return arr
}
Copy the code

Partition (arr, left, right) let index = partition(arr, left, right)

Quick (arr, left, index – 1) means to split the small array again

Quick (arr, index, right) means to split the large array again

If there are at least two elements in the array, the left and index-1 will both refer to the same element, so there is no need to split them.

When you have only one array, you can’t split it anymore.

Now the array is sorted. Why is it sorted? Go back to the picture above.

So why does it have to be <=

When the array is already sorted after being split

arr = [2.4.6.11.33.55.77]
Copy the code

Low === 3,height === 4

function partition(arr, low, height) {
  const pivot = arr[Math.floor((low + height) / 2)] // pivot === arr[3] === 11
  let i = low // i === 3
  let j = height // j === 4
  while (i < j) {
    while (arr[i] < pivot) i++ / / to skip
    while (pivot < arr[j]) j-- // arr[j] === arr[3] === 11
    if (i < j) { // I === 3, j === 3, skip
      [arr[i], arr[j]] = [arr[j], arr[i]]
      i++
      j--
    }
  }
  return i // i === 3
}
Copy the code

Then enter the

function quick(arr, low, height) {
  // low === 3, height === 4
  if (arr.length > 1) {
    const index = partition(arr, low, height) // index = 3
    if (low < index - 1) quick(arr, low, index - 1) / / 3 < 2
    if (index < height) quick(arr, index, height) // quick(arr, index, height)
  }
  return arr
}
Copy the code

Here’s the point. Enter now

quick(arr, index, height) // index === 3, height === 4
Copy the code

We’re going to start repeating this step indefinitely.

Why is that?

The problem is

After grouping 3~4, we should return 4

So that it can be divided into subsequent groups

3 minus 4 minus 1 and 4 minus 4

If this is the case, there is only one element left in the group and it will not continue to be divided

If I return 3

This is the grouping case

3 – (3, 1) and 3 ~ 4

Will mistakenly think that can continue to score, constantly cycle points 3~4

Efficiency (hurry)

Among other things, there is a significant improvement over merge sort: no extra space is required!

The time complexity isAnd the performance is usually more complex than othersThe sorting algorithm is better.

Efficiency later seriously write, there is no time now.

And then, merge sort taught us that quicksort is unstable