First, the original intention of writing this article

Hi, I’m Xiaoyu.

When brushing zhihu recently, I accidentally saw such a question — “Ruan Yifeng version of quick sorting is completely wrong” whether there is a factual error?

Miss Winter took a screenshot of a student’s message on a certain platform and put it in her answer. One sentence left a deep impression on me:

The front ceiling is really too low.

I personally have a little respect for Ruan Yifeng teacher. I remember when I was a beginner in college, I often read Ruan’s JS tutorial. Even after I started working, I occasionally went to check his Flex layout tutorial.

The image of a teacher with a passion for technology, and of my own field, being trashed, successfully fueled my desire to win.

I aggressively opened my VSCode.

Is quicksort difficult

I, for one, have always believed that all technical terms are paper tigers.

So in order to implement quicksort, first of all, what is it?

Here’s how Wikipedia defines quicksort:

Quicksort uses a Divide and conquer strategy to Divide a list into two subsequences, smaller and larger, and then sort the two recursively.

Does that make any sense? Build on your success and start writing code!

First, declare a function sortArray that takes an array numS as an argument.

If the length of the array nums is less than or equal to 1, you can simply return the array.

function sortArray(nums) {
  if (nums.length <= 1) {
    returnnums; }}Copy the code

Select one of the nums arrays as a reference (I prefer not to call it a reference), for the subsequent segmentation of the size of the two subarrays as a reference, here I will choose the middle one, reservations.

function sortArray(nums) {
  if (nums.length <= 1) {
    return nums;
  }

  var pivotIndex = Math.floor(nums.length / 2);
  var pivotValue = nums[pivotIndex];
}
Copy the code

Declare two temporary arrays, left and right, and iterate over nums:

  • Smaller than the referenceleft;
  • Larger than or equal to a referenceright;
  • When the reference itself is encountered, skip the current loop.
function sortArray(nums) {
  if (nums.length <= 1) {
    return nums;
  }

  var pivotIndex = Math.floor(nums.length / 2);
  var pivotValue = nums[pivotIndex];

  var left = [];
  var right = [];

  for (var i = 0; i < nums.length; i += 1) {
    if (i === pivotIndex) {
      continue;
    }

    if (nums[i] < pivotValue) {
      left.push(nums[i]);
    } else{ right.push(nums[i]); }}}Copy the code

Finally, there is the familiar recursive operation, which is repeated over and over again on the two subarrays left and right.

function sortArray(nums) {
  if (nums.length <= 1) {
    return nums;
  }

  var pivotIndex = Math.floor(nums.length / 2);
  var pivotValue = nums[pivotIndex];

  var left = [];
  var right = [];

  for (var i = 0; i < nums.length; i += 1) {
    if (i === pivotIndex) {
      continue;
    }

    if (nums[i] < pivotValue) {
      left.push(nums[i]);
    } else{ right.push(nums[i]); }}return sortArray(left).concat([pivotValue], sortArray(right));
}
Copy the code

At the end of each recursion, a concatenated array of sortArray(left), [pivotValue], and sortArray(Right) is returned and given to the last recursion for concatenation.

At the end of the recursion, the entire array is sorted.

This is similar to the truth that the upper beam is not straight and the lower beam is crooked. The lower beam has been righted, and the upper beam is naturally positive (ridicule: what rotten metaphor……) .

Aye? Is quicksort so easy to beat? It’s not.

This is what I think most people’s first instinct is to write.

Advantages:

  1. It’s easy to imagine that indirectly protecting our brains makes us feel fulfilled in the short term;
  2. The code is clean enough that even beginners can understand what each line of code is doing.

Disadvantages:

  1. It’s easy to get arrogant and indirectly hinder your ability to improve your code.
  2. The biggest problem with this approach is that two temporary arrays need to be created for each recursion, which wastes memory and makes space complexity terrible.

Its results in LeetCode are as follows:

  • Execution time: 152 ms, beating 71.95% of all JavaScript commits;
  • Memory consumption: 60.5 MB, beating 6.37% of all JavaScript commits.

Sure enough, waste is the greatest shame! Time complexity needs to be improved, and space complexity needs saving even more. Otherwise, it would be ridiculed: is this the quicksort written by the front end students?

Three, I’m just quick sort in place

Yeah, that’s right, this time I’m just going to do a quick sort in place instead of creating a temporary array left and right.

I’ll post the code in respect and explain it in detail later.

function swap(nums, left, right) {
  var template = nums[left];
  nums[left] = nums[right];
  nums[right] = template;
}

function partition(nums, left, right) {
  var pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
  var pivotValue = nums[pivotIndex];

  swap(nums, pivotIndex, right);

  for (var i = left; i < right; i += 1) {
    if (nums[i] <= pivotValue) {
      swap(nums, left, i);
      left += 1;
    }
  }

  swap(nums, left, right);

  return left;
}

function quickSort(nums, left, right) {
  if (left >= right) {
    return;
  }

  var nextPivot = partition(nums, left, right);
  quickSort(nums, left, nextPivot - 1);
  quickSort(nums, nextPivot + 1, right);
}

function sortArray(nums) {
  quickSort(nums, 0, nums.length - 1);
  return nums;
}
Copy the code

I’m sorry, I might have to eat my word, I’m too lazy to explain, can I give you a video to understand yourself?

The video is here: 1 second to remember quicksort

Although also a clickbait, but the video animation is still very lively, I was watching this animation to write such a great quicksort.

How great? Take a look at leetcode’s results:

  • Execution time: 104 ms, beating 99.38% of all JavaScript commits;
  • Memory consumption: 49.3 MB, beating 75.22% of all JavaScript commits.

I’m quite satisfied, aren’t you?

Four, the conclusion to say

In a word: I vindicate the front-end XDJM folks!

River’s lake road far, predestined relationship goodbye!