Understand quicksort

Quicksort is a partition commutative sort proposed by C.R.A.Hoare in 1962. It adopted a divide-and-conquer strategy, often called the divide-and-conquer method. Quicksort is an unstable sort method.

Quicksort operation procedure

  1. Take a number as a benchmark. (The benchmark will be named belowtemp)
  2. All the decimals come before it, and all the big numbers come after it, sotempThere are two subintervals on the left and the right.
  3. Two subintervals are not necessarily ordered internally. So repeat 1,2 in each interval until each interval has only one number.No nesting dolls?

Since the processing is repeated within each interval, we can implement it either with recursive functions (which take up stack space) or with a while loop.

Quicksort can easily work with large, unordered arrays, but performs poorly when used with highly ordered (even fully ascending, descending, and identical elements) arrays.

The solution provided by digging pit method

Step 2 mentioned in the previous paragraph can be implemented in a number of ways, but the idea is similar. In this case, the digging method is used. We first prepare:

  • Two “Pointers” (although they are really just array labels, they will be referred to as Pointers for ease of understanding)lowandhigh, pointing to the beginning and end of the array respectively, andhighOnly toOn the leftMobile,lowOnly torightMobile.
  • By default, the first element of the array is saved totempIn the middle.

To put it another way, before the program starts, a hole is dug at arr[low], and the number at that position is moved to Temp.

There is one big premise: low < high must be true when the function is called, otherwise the recursion will not continue. Because low==high means there’s only one element in this array, so we don’t have to sort anymore.

When the program runs, the low pointer does not move, and the high pointer determines whether the value it currently points to is greater than temp. Move to the left if the condition is met, otherwise the high pointer stops and overwrites the currently pointed value to the arr[low] position. (Win the prize in the first judgment =D)

Or the number in the high position is dug out and filled in the hole in the low position.

high
low
temp
low
arr[high]

In other words, the number in the low position is dug out to fill the hole left by the high pointer position in the previous step.

The high pointer starts to move left again until it finds a number greater than or equal to temp, then digs it out and fills in the place of the low pointer and pauses. Then the low pointer moves right again until it finds a number less than temp, then digs it out and fills in the high pointer…… The high and low Pointers have been moving alternately opposite each other.

At some point the high and low Pointers will point to the same place. Now you don’t need to move the high and low Pointers anymore, you just need to put the temp value that was originally dug into this hole.

We can now see that the original array has been divided into three parts: numbers smaller than temp, temp, and arrays larger (or equal) than temp.

Just recurse for Smaller and Greater again and repeat the steps described earlier.

Java quick sort based on digging method

 static void quickSortJ(Integer[] arr, int start, int end) {
        if (start < end) {
            Integer low = start;
            Integer high = end;
            Integer temp = arr[low];

            while (low < high) {

                while (high > low && arr[high] >= temp) high--;
                if (high > low) arr[low] = arr[high];
                while (high > low && arr[low] < temp) low++;
                if (high > low) arr[high] = arr[low];
                
            }
            
            arr[high] = temp;
            quickSortJ(arr, start, low - 1);
            quickSortJ(arr, high + 1, end); }}Copy the code

I want [Smaller[], Temp, Greater[]]!

We must be able to split the array into [Smaller[], temp, Greater[]] after a round of sorting (left/right pointer, hole digging, etc.). Can we get Smaller and Greater in a simpler and more lazy way? In Scala, you can use the filter directly to filter out numbers smaller (or larger) than temp. Such as:

Arr. Filter (x => x > temp) // Filter is still Array[].

Then continue recursion for Smaller[] and Greater[]. Java flow processing can also achieve similar logic, but more troublesome.

Quicksort in Scala


  def quickSortScl(arr: Array[Int) :Array[Int] = {
    if (arr.length <= 1)
       arr
    else {
      // Temp does not take the first element, but the middle element.
      val temp =arr(arr.length/2)
      // Return a SmallerThanTemp[],temp,GreaterThanTemp[]].
      Array.concat(
        quickSortScl(arr.filter(x => x<temp)),
        // If multiple elements are equal, the number of elements in the array is greater than 1.
        arr.filter(x => x==temp),
        quickSortScl(arr.filter(x => x>temp))
      )
    }
  }
Copy the code

Portal link

  • Why is quicksort fast?