In-depth analysis of the quick sort algorithm

[[121946]]

Preface

Previously, I wrote an article in this blog, a tutorial on the quick sort algorithm, and many netizens said that this article was easy to understand. However, later, a netizen named algorithm__ pointed out, "How did the quick sort algorithm come up with the sequence step by step? It's like a P and NP problem. If you know the solution, it's not difficult to prove it. But if you don't know how to deduce it bit by bit and step by step before solving it, how difficult is that?"

In fact, I have thought about this question many times. I have mentioned it many times in my blog before. So why do many people read the quick sort algorithm I wrote, but after a while, they are no longer clear about what quick sort is?

"A big part of the reason is that we only know the surface but not the inside, and only know the use but not the essence. Many things can be seen from the essence. But most people don't do this. As a result, they read and forget, forget and read again. In this way, in the repeated memorization of knowledge, they have never been able to analyze the essence, thus forming a bad cycle.

So, in the final analysis, to learn something, you must not only be able to use it freely, but also understand its principles, ins and outs, and essence. As Mr. Hou Jie said, it is not very smart to only know how to use something but not its principles. The question you raised is very good. I will write another article to thoroughly explain how the quick sort algorithm is designed and how it came about step by step. "

Ok, now I will thoroughly analyze this quick sort algorithm, hoping to make readers truly understand this algorithm, know its ins and outs, and understand its internal principles. This article focuses on analyzing the process source and time complexity of the quick sort algorithm.

1. The initial version of quick sort

The algorithm idea of ​​quick sort (at this time, it was not called quick sort) was originally proposed by a man named CAR Hoare. The specific version of the algorithm idea he gave is as follows:

HOARE-PARTITION(A, p, r)

 x ← A[p]
 i ← p - 1
 j ← r + 1
 while TRUE
 do repeat j ← j - 1
 until A[j] ≤ x
 repeat i ← i + 1
 until A[i] ≥ x
 if i < j
          then exchange A[i] ↔ A[j]
 else   return j

Later, this version had many similar variants. Below, we will analyze them in detail.

2. Specific Analysis of Hoare's Version

Hoare elaborates on this in Question 7-1 of Chapter 7*** of Introduction to Algorithms.

As we have seen above, Hoare's quick sort version can be sorted by comparing the two pointers pointing to the head and the tail respectively.

Below, we analyze this version:

I. Two pointers, i points to the head of the sequence, and j points to the tail, that is, i=1, j=n. Take the first element ki in the array as the principal element, that is, key<-ki (assignment).

II. Assignment operation (Note: "->" means assignment):

j (find the smaller one), from right to left, continuously --, until encountering the first element kj smaller than key, ki<-kj.

i (find the larger one), from left to right, keep ++ing until you encounter the first element ki that is larger than key, kj<-ki.

III. Continue in the above way until i and j meet, ki=key, the first round of sorting is completed, and then repeat step II recursively.

When the HOARE-PARTITION process is completed, every element in A[p..j] (there is a printing error in the second edition of the Chinese version of the Introduction to Algorithms, and it is printed as A[p..r]) is less than or equal to every element in A[j+1..r]. HOARE-PARTITION is different from the standard PARTITION partitioning method to be introduced below. HOARE-PARTITION always puts the pivot value into one of the two partitions A[p..j] and A[j+1..r]. Because p<<j<<r, this partitioning will always end.

Next, let's take a look at the operation process of the above HOARE-PARTITION partitioning method on the array A=[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21], as follows:

i (find big) (find small) j

13 19 9 5 12 8 7 4 11 2 6 21

ij

13 19 9 5 12 8 7 4 11 2 6 21

ij

6 19 9 5 12 8 7 4 11 2 13 21

j i

6 2 9 5 12 8 7 4 11 19 13 21

ij

6 2 9 5 12 8 7 4 11 19 13 21

ij

4 2 9 5 12 8 7 6 11 19 13 21

ij

4 2 5 9 12 8 7 6 11 19 13 21

.....

2 4 5 6 7 8 9 11 12 13 19 21

3. Hoare variant

I. Take two pointers i and j. At the beginning, i=2 and j=n, and we make sure that when the sorting is finally completed, the number of the left subsequence is <= the right subsequence.

II. Correct position and keep changing

i-->(i moves from left to right, looking for an element larger than the last one)

By comparing ki with k1, if Ri will eventually become part of the left subsequence after the partition,

Then i++, and continue i++ until a subsequence Ri (larger) belonging to the right is encountered.

<--j (j moves from right to left, looking for an element smaller than the last one)

Similarly, j--, until a smaller element Rj (smaller) belonging to the left subsequence is encountered,

In this way, when i<j, exchange Ri and Rj, that is, rearrange the positions of the ma, put the smaller one on the left and the larger one on the right.

III. Then process the divided records in the same way until i and j meet. In this way, the positions of Ri and Rj are constantly exchanged to complete the sorting of the entire sequence.

For example, as follows (2 is the principal element):

i-> <-j (find smaller)

2 8 7 1 3 5 6 4

The element 4 pointed to by j is greater than 2, so j--,

i <--j

2 8 7 1 3 5 6 4

During this process, if j does not encounter an element smaller than 2, j will continue to increase until j points to 1.

ij

2 8 7 1 3 5 6 4

At this moment, 8 and 1 are swapped.

ij

2 1 7 8 3 5 6 4

At this moment, the element pointed to by i is 1, which is smaller than 2, so i does not move, and j continues - it never encounters an element smaller than 2, and finally stops at 7.

ij

2 1 7 8 3 5 6 4

***, the element 1 pointed to by i is exchanged with the first element k1 in the sequence, that is, 2.

i

[1] 2 [7 8 3 5 6 4]

In this way, 2 divides the entire sequence into two parts. Next, the remaining numbers to be sorted are recursively sorted for the second and third rounds....

From the above process, we can roughly see the clumsiness of this algorithm. For example, in the first step, when j does not find an element smaller than 2, it needs to keep moving forward, j--. Second, after the element pointed to by i is exchanged, it cannot be guaranteed that the element pointed to by i at this moment is definitely smaller than 2, that is, the i pointer may continue to stay in the original place and cannot move. Such a stay will inevitably take a lot of time.

Later, Sedgewick named it "Quick Sort" because of its fast sorting speed, and Quick Sort was born. It eventually became famous and became one of the 10 greatest algorithms of the 20th century.

OK, next, let's look at Hoare's variant algorithm. As follows, sort the sequence 3 8 7 1 2 5 6 4:

1. j--, until it encounters the first element 2 in the sequence that is smaller than the key value 3, assigns 2 to ki, and j now points to an empty element.

i j

3 8 7 1 2 5 6 4

ij

=> 2 8 7 1 5 6 4

2. i++, pointing to 8, resets 8 to the blank space of the element pointed to by j, and the element pointed to by i is empty again:

ij

2 8 7 1 5 6 4

ij

=> 2 7 1 8 5 6 4

3. j continues --, encounters 1, which is still smaller than 3 (the key value saved in advance), and assigns 1 to the blank space pointed to by i:

ij

2 7 1 8 5 6 4

=> 2 1 7 8 5 6 4

4. Similarly, i continues to ++ and encounters 7, which is greater than key. 7 is assigned to the blank space pointed to by j. After that, i and j meet. The last round ends:

ij

2 1 7 8 5 6 4

ij

=> 2 1 7 8 5 6 4

5. ***, assign the previously saved key, 3, to ki, i.e. the blank space pointed to by i, and we get:

[2 1] 3 [7 8 5 6 4]

So, the whole thing is like this:

3 8 7 1 2 5 6 4

2 8 7 1 3 5 6 4

2 3 7 1 8 5 6 4

2 1 7 3 8 5 6 4

2 1 3 7 8 5 6 4

2 1 3 7 8 5 6 4

Subsequent supplement:

What if the sequence to be sorted is a reverse sequence? Ok, to make it clearer, let's take another example to sort the sequence 9 8 7 6 5 4 3 2 1:

9 8 7 6 5 4 3 2 1 //9 is the principal element

1 8 7 6 5 4 3 2 //j searches from right to left for the smallest number, finds 1, and assigns it to the ***th one

1 8 7 6 5 4 3 2 //i searches from left to right for the largest number, but does not find it until it meets j

1 8 7 6 5 4 3 2 9 //***, fill in 9.

As mentioned above, when the array is already sorted in reverse order, we can easily know that sorting the array requires O(N^2) time complexity. Later in the article, we will analyze the time complexity of quick sort in detail.

***, write a program to implement this algorithm, as follows, I believe, I don’t need to explain too much:

 int partition( int data[], int lo, int hi) //Quoted from whatever.   
 
 { 
 
 int key=data[lo]; 
 
 int l=lo; 
 
 int h=hi; 
 
 while (l<h) 
 
 { 
 
 while (key<=data[h] && l<h) h--; //Search for the smaller one in the high position, and if found, move it to the front   
 
 data[l]=data[h]; 
 
 while (data[l]<=key && l<h) l++; //Search for the larger one in the lower position, and if found, move it to the back   
 
 data[h]=data[l]; 
 
 } // In this way, the small one is in front and the big one is in the back, divided into two   
 
 data[l]=key; 
 
 return l; 
 
 }

Subsequent supplement: For example, as follows (only the first round of sorting is explained):

3 8 7 1 2 5 6 4

2 8 7 1 5 6 4

2 7 1 8 5 6 4

2 1 7 8 5 6 4

2 1 7 8 5 6 4

2 1 3 7 8 5 6 4 //***Fill in, keyword 3

Seeing this, I wonder if you readers have thought of the second version of the quick sort in my previous article? Yes, the above program is the second version in that article. I will pull out the program, and you will understand it at a glance:

 void quicksort(table *tab, int left, int right)
 {
 int i,j;
 if (left<right)
 {
 i=left;j=right;
 tab->r[0]=tab->r[i]; //Prepare to divide based on the value of the leftmost element this time, save its value first  
 do  
 {
 while (tab->r[j].key>tab->r[0].key&&i<j)
 j--; //Find the first position j that is smaller than the standard value from right to left  
 if (i<j) //Found, position is j  
 {
        tab->r[i].key=tab->r[j].key;i++; 
 
 } //Put the jth element at the left and reset i   
 
 while (tab->r[i].key<tab->r[0].key&&i<j) 
 
 i++; //Find the first position i that is greater than the standard value from left to right   
 
 if (i<j) //Found, position is i  
 {
        tab->r[j].key=tab->r[i].key;j--;
 } //Put the i-th element at the right end and reset j   
 
 } while (i!=j);
 tab->r[i]=tab->r[0]; //Put the standard value into its final position, and the division is finished  
 quicksort(tab,left,i-1); //Recursively call this function on the left half of the standard value  
 quicksort(tab,i+1,right); //Recursively call this function for the right half of the standard value  
 }
 }

I think, so far, I have explained it clearly enough. If you still don't understand, well, stretch out your fingers and count.... OK, let me ask the readers another question: In this case, i is searched from left to right, and when the first element is larger than key (the first element in the array is set as key), kj is reset, and j is searched from right to left, and when the first element is smaller than key, ki is reset. Of course, in this process, i and j are constantly changing, pointing to different elements through ++ or --.

Do you think of any situations in real life that are similar to the idea of ​​the quick sort algorithm? OK, when you think of it, tell me, it's not too late. :D.

4. Optimized version of quick sort

Later, N. Lomuto proposed a new version, which is the first version described in the quick sort algorithm, that is, the optimized PARTITION procedure, which is now written in the book Introduction to Algorithms.

The key to the quick sort algorithm is the PARTITION procedure, which performs an in-place reordering of A[p..r]:

PARTITION(A, p, r)

 x ← A[r] // Take the last element, A[r] as the principal element  
 i ← p - 1
 for j ← p to r - 1 //Note, j points from p to r-1, not r.   
 
 do   if A[j] ≤ x
 then i ← i + 1
                exchange A[i] <-> A[j]
 exchange A[i + 1] <-> A[r]
 return i + 1

Then, recursively sort the entire array:

 QUICKSORT(A, p, r)
 if p < r
 then q ← PARTITION(A, p, r) //key  
         QUICKSORT(A, p, q - 1)
         QUICKSORT(A, q + 1, r)

Take the example at the beginning: 2 8 7 1 3 5 6 4, but the difference is that it no longer takes the first element as the main element, but takes the first element 4 as the main element, and the i and j pointers both start from the beginning, j is in front and i is in the back. i refers to the previous position of the element, and j refers to the first element in the sequence to be sorted.

one,

ip/j-->

2 8 7 1 3 5 6 4 (pivot)

j points to 2<=4, so i++, i also points to 2, 2 and 2 are swapped, and the original array remains unchanged.

j moves back until it points to 1..

two,

j (pointing to 1) <= 4, so i++, i points to 8,

ij

2 8 7 1 3 5 6 4

So 8 and 1 are swapped, and the array becomes:

ij

2 1 7 8 3 5 6 4

3. j moves back and points to 3, 3<=4, so i++

i now points to 7,

ij

2 1 7 8 3 5 6 4

So 7 and 3 are swapped, and the array becomes:

ij

2 1 3 8 7 5 6 4

4. j continues to move backward and finds that there is no number smaller than 4, so it executes to the last step.

That is line 7 of the PARTITION(A, p, r) code section above.

Therefore, i moves back one unit and points to 8

ij

2 1 3 8 7 5 6 4

A[i + 1] <-> A[r], that is, 8 and 4 are swapped, so the array eventually becomes the following form,

2 1 3 4 7 5 6 8

OK, the first round of quick sort is completed. The following process is omitted. However, there is a question, can you find the optimization of this version compared with the above version?

5. In-depth analysis of quick sort

Let's analyze the above optimized version in detail.

 PARTITION(A, p, r)
 x ← A[r]
 i ← p - 1
 for j ← p to r - 1
 do   if A[j] ≤ x
 then i ← i + 1
                  exchange A[i] <-> A[j]
 exchange A[i + 1] <-> A[r]
 return i + 1

Let's sort the following array, and the change process at each step is:

ip/j

2 8 7 1 3 5 6 4 (pivot)

ij

2 1 7 8 3 5 6 4

ij

2 1 3 8 7 5 6 4

i

2 1 3 4 7 5 6 8

From the above process, we can see that j scans the entire array once, and once it encounters an element smaller than 4, i will ++, and then kj and ki will be exchanged. So why does i have to ++ when j finds an element smaller than 4? Think about it, if i always stays in the same place, wouldn't ki, which is exchanged with kj every time, be the same element? In this case, what's the point of sorting?

Therefore, j leads the way and i follows behind j. Whenever j encounters an element smaller than 4, i takes a step forward and assigns the element smaller than 4 found by j to i. Then, j moves forward again.

To put it in a metaphor, you can think of it this way: every step that i takes must be an element smaller than 4, otherwise, i cannot move forward. It is like j is a pioneer, paving the way for i, putting small elements in front of i as a springboard to pave the way for it to move forward.

At this point, j has scanned to *** and has completely checked out all elements smaller than 4. There is only one main element 4, which is handed over to i for processing, because in the first step, exchange A[i + 1] <-> A[r]. In this way, not only is it completely ensured that all elements smaller than 4 are exchanged to the front of the array, but also the larger elements that j has not processed before are exchanged to the back, and the time complexity is O(N). You have to admire the cleverness of this algorithm design.

So, I have a question, can the above PARTITION(A, p, r) version be changed to this?

I hope readers will think about:

 PARTITION(A, p, r) //Please think about the version.  
 x ← A[r]
 i ← p - 1
 for j ← p to r //Let j point to the last element r from p  
 do   if A[j] ≤ x
 then i ← i + 1
                  exchange A[i] <-> A[j]
 exchange A[i + 1] <-> A[r] // remove this *** step  
 return i //Return i, no longer return i+1.  

6. Comparison between Hoare variant and optimized version

Now, let's discuss a problem. In the quick sort, for the division of the sequence, we can see that there are already two versions above. So which of these two versions is better? Ok, no hurry, let's compare:

For your convenience, let's paste the respective algorithms.

Hoare variant:

HOARE-PARTITION(A, p, r)

 x ← A[p] // Take the first element as the principal element  
 i ← p - 1
 j ← r + 1
 while TRUE
 do repeat j ← j - 1
 until A[j] ≤ x
 repeat i ← i + 1
 until A[i] ≥ x
 if i < j
          then exchange A[i] ↔ A[j]
 else   return j

The optimized version from the algorithm introduction:

 PARTITION(A, p, r)
 x ← A[r] // Take the last element, A[r] as the principal element  
 i ← p - 1
 for j ← p to r - 1
 do   if A[j] ≤ x
 then i ← i + 1
                  exchange A[i] <-> A[j]
 exchange A[i + 1] <-> A[r]
 return i + 1

Let's first take the example of the Hoare version above and sort the sequence 3 8 7 1 2 5 6 4:

Hoare variant (with 3 as the principal element and red as the principal element):

3 8 7 1 2 5 6 4

2 8 7 1 5 6 4 //Swap once, compare 4 times

2 7 1 8 5 6 4 //Swap once, compare once

2 1 7 8 5 6 4 //Swap once, compare once

2 1 7 8 5 6 4 //Swap 1 time, compare 0 times

2 1 3 7 8 5 6 4 //Total 4 exchanges and 6 comparisons.

// Elements 3, 8, 7, 1, 2 are moved. The moving range is: 2+3+1+2+4=12.

Optimized version (with 4 as the pivot):

3 8 7 1 2 5 6 4 //Swap 3 and 3, no need to move elements, compare once

3 1 7 8 2 5 6 4 //Swap once, compare three times

3 1 2 8 7 5 6 4 //Swap once, compare once

3 1 2 4 7 5 6 8 //Swap once, compare twice.

//Completed, a total of 4 exchanges and 7 comparisons.

// Elements 8, 7, 1, 2, 4 are moved. The moving range is: 6+2+2+2+4=16.

Another example: sort the sequence 2 8 7 1 3 5 6 4:

Hoare variant:

2 8 7 1 3 5 6 4

1 8 7 3 5 6 4 //Swap once, compare 5 times

1 7 8 3 5 6 4 //Swap once, compare once

1 2 7 8 3 5 6 4 //Swap 0 times, compare 1 time. Fill in 2, done, a total of 2 swaps and 7 comparisons.

Optimized version:

2 8 7 1 3 5 6 4 //Exchange 2 and 2, compare once

2 1 7 8 3 5 6 4 //Swap once, compare three times

2 1 3 8 7 5 6 4 //Swap once, compare once

2 1 3 4 7 5 6 8 //Swap 1 time, compare 2 times. Completed, a total of 4 swaps and 7 comparisons.

As you can see, these two examples do not prove anything. Which version is more efficient still needs further verification or mathematical proof. Ok, I will prove it again when I find more favorable evidence.

7. Time complexity of quick sort algorithm

OK, I think you have fully understood this quick sort, so I think you should be able to quickly determine that the average time complexity of the quick sort algorithm is O(nlgn). Why? Because you see, how long does it take for j,i to scan the array once? Yes, scanning once is of course O(n), so how many times to scan the list, lgn to n times, the fastest lgn, the slowest n. And it can be proved that the average time complexity of quick sort is O(n*lgn).

In the most balanced partition possible by PARTITION, each subproblem obtained cannot be larger than n/2.

Because one of the subproblems has a size of |_n/2_|. The other subproblem has a size of |-n/2-|-1.

In this case, quick sort is much faster.

T(n)<=2T(n/2)+O(n). It can be proved that T(n)=O(nlgn).

Here is a simple proof of a recursive tree:

In the three steps of the divide-and-conquer algorithm, we assume that the time taken for the decomposition and merging process is D(n) and C(n) respectively. Let T(n) be the time taken for processing a sequence of size n, the number of subsequences, each subsequence is 1/b of the original sequence, and α is the time taken for decomposing each problem into α subproblems. Then the time taken is:

O(1) if n<=c

T(n) =

αT(n/b) + D(n) + C(n)

In quick sort, α is 2, b is also 2, then decomposition (that is, taking a reference point, which can be considered as 1), merging (merging the array to n), so D(n) + C(n) is a linear time O(n). So the time becomes:

T(n) = 2T(n/2) + O(n).

As shown in the figure above, the time complexity of each layer is: O(n). There are Lgn layers in total, and each layer is cn, so the total time consumed is cn*lgn; the total time is:

cn*lg2n+cn = cn(1+lgn) which is O(nlgn).

For a rigorous mathematical proof of T(n)<=2T(n/2)+O(n)=>T(n)=O(nlgn), please refer to Chapter 4, Recursion, in Introduction to Algorithms.

Then, I would like to ask readers a question. What do you think of the time complexity of the quick sort algorithm? Do you think of the time complexity of merge sort? Do you think of binary search? Do you think of the height lgn of a red-black tree with n nodes? Do you think of...

8. What comes from quick sort

I have thought about the above mentioned things a long time ago. At this moment, I thought of a Dutch flag problem I saw a few days ago. At that time, I briefly discussed this problem with algorithm__ and gnuhpc. Now, I will also solve this problem in detail:

Problem description:

We arrange the random red, white and blue balls into an ordered group of red, white and blue balls of the same color. The reason why this problem is called the Dutch flag is that we can imagine the red, white and blue balls as strips, which form the Dutch flag after being arranged in an orderly manner. As shown in the figure below:

[[121948]]

This problem is similar to the partition process in quicksort. However, we need to use three pointers, one for begin, one for current, and one for end, and swap them in pairs.

1. Current traverses the entire array sequence, and current points to 1 and does not move.

2. Current refers to 0, which is exchanged with begin, and then current++, begin++,

3. Current refers to 2, which is exchanged with end. Then, current does not move, end--.

Why? In the third step, current refers to 2. After exchanging with end, current does not move. That's right, just as algorithm__ says: the reason why current is exchanged with begin, current++, begin++, is because there is no worry. But after current is exchanged with end, current does not move, end--, because there is worry.

Why? Because think about it, your ultimate goal is to arrange 0, 1, and 2 in order. Imagine that in the third step, before current is swapped with end, if end previously pointed to 0, and after current is swapped, current now points to 0. At this time, can current move? It cannot move. It points to 0 and has to swap with begin.

Ok, after saying so much, you may not understand it very well. Just quote the diagram of gnuhpc and it will be clear at a glance:

The main code of this program is:

 //Quoted from gnuhpc  
 while ( current <= end )
 {
 if ( array[current] == ​​0 )
 {
      swap(array[current],array[begin]);
 current++;
 begin++;
 }
 else   if ( array[current] == ​​1 )
 {
 current++;
 }
 else   //When array[current] = 2  
 {
      swap(array[current],array[end]);
 end--;
 }
 }

It seems that this question has little to do with this article, but, firstly, the process of quick sorting partitions in the rest of this article is similar, and secondly, this question triggered a little thinking, which eventually led to this article. I almost forgot that I haven't answered the question raised at the beginning of this article. So, how did the quick sort algorithm come up with it, and how was it invented step by step? The answer is simple: observe more and think more.

Ok, let's test it to see if you have the habit of observing and thinking more: I don't know if anyone has really thought about bubble sorting. If so, have you ever thought about how to improve the bubble sorting sequence? Ok, I won't say much about the rest, just post the following picture:

This article ends.

Author: July