Quick sort algorithm popularization tutorial

[[121950]]

Without further ado, let's get into the topic of this article, the sorting algorithm.

As we all know, the quick sort algorithm is the highlight of the sorting algorithm.

Therefore, this article starts with quick sort.

---------------------------------------------------------------

1. Basic characteristics of the quick sort algorithm

Time complexity: O(n*lgn)

Worst case: O(n^2)

Space complexity: O(n*lgn)

Unstable.

Quick sort is a sorting algorithm that takes an average of O(nlgn) time and a worst-case time of O(n^2) for an input array of n numbers.

It is usually the best choice for sorting. Because, the fastest sorting based on comparison can only reach O(nlgn).

2. Description of the Quick Sort Algorithm

Introduction to Algorithms, Chapter 7

Quick sort is based on the divide-and-conquer mode.

The divide-and-conquer process for sorting a typical subarray A[p...r] is three steps:

1. Decomposition:

A[p..r] is partitioned into two (possibly empty) subarrays A[p ..q-1] and A[q+1 ..r], such that

A[p ..q-1] <= A[q] <= A[q+1 ..r]

2. Solution: Sort the subarrays A[p ..q-1] and A[q+1 ..r] by recursively calling quick sort.

3. Merger.

3. Quick sort algorithm

Version 1:

QUICKSORT(A, p, r)

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

Array Partitioning

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]
 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

Ok, let's give a specific and complete example.

To quickly sort the following array,

2 8 7 1 3 5 6 4 (pivot)

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, so 8 and 1 are swapped.

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, so 7 and 3 are swapped.

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 pass of quick sort is completed.

4 Divide the entire array into two parts, 2 1 3, 7 5 6 8, and then recursively quickly sort the two parts separately.

ip/j

2 1 3 (pivot)

2 and 2 are swapped, no change, then 1 and 1 are swapped, still no change, ***, 3 and 3 are swapped, no change,

Finally, 3 split 2 1 3 into two parts, 2 1, and 3.

Then recursively sort 2 1, and the final result becomes 1 2 3.

7 5 6 8 (pivot), 7, 5, 6, are all smaller than 8, so the last round is still 7 5 6 8,

However, at this moment 8 divides 7 5 6 8 into 7 5 6, and 8. [7 5 6->5 7 6->5 6 7]

Then recursively sort 7 5 6, and the final result becomes 5 6 7 8.

OK, all processes and analysis are completed.

***, look at the picture I drew:

Quick sort algorithm version 2

However, this version no longer selects the last element of the array (as in the first version above) as the main element.

Instead, choose the first element in the array as the pivot.

 /******************************************************/  
 /* Function: Quick sort algorithm */  
 /* Function parameter: pointer variable tab of structure type table */  
 /* Subscripts of the left and right boundaries of integer variables left and right */  
 /* Function return value: void */  
 /* File name: quicsort.c Function name: quicksort () */  
 /******************************************************/  
 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  
 }
 }

----------------

Ok, let's use the same array as above and apply version 2 of the quick sort algorithm to demonstrate the sorting process:

This time, the first element in the array, 2, is used as the pivot.

2(main) 8 7 1 3 5 6 4

Please take a closer look:

2 8 7 1 3 5 6 4

i-><-j

(Find the big one) (Find the small one)

1.j

j finds the first element 1 that is less than 2, and assigns 1 to (overwrites and resets) the element 2 pointed to by i

get:

1 8 7 3 5 6 4

ij

II.

i finds the first element 8 greater than 2, and assigns 8 to (overwrites and resets) the element pointed to by j (NULL<-8)

1 7 8 3 5 6 4

i <-j

3.j

j continues to move left, and before it meets i, it does not find an element smaller than 2, so the process ends.

***, main element 2 is added.

After the ***th fast sort, the array becomes:

1 2 7 8 3 5 6 4

The second trip,

7 8 3 5 6 4

i-><-j

(Find the big one) (Find the small one)

1.j

j finds 4, which is smaller than the pivot 7, and assigns 4 to the position of 7.

get:

4 8 3 5 6

i->j

II.

i finds the first element 8 that is larger than 7, and 8 covers the element pointed to by j (NULL)

4 3 5 6 8

ij

4 6 3 5 8

i->j

i and j meet, ending.

Third trip:

4 6 3 5 7 8

......

Below, the analysis principle is consistent and will be skipped.

The results of *** are shown in the figure below:

1 2 3 4 5 6 7 8

I believe that after a detailed analysis of the above content, you must have understood it.

***, here is a picture I drew about this sorting process:

End. Added on January 5.

OK, of the two algorithms mentioned above, you only need to understand one.

------------------------------------------------------------------

5. The worst case and fastest case of quick sort.

The worst case occurs when the two regions generated by the partitioning process contain n-1 elements and one 0 element respectively.

That is, assuming that this partitioning occurs in every recursive call of the algorithm, the partitioning cost is O(n).

Because after recursively calling an array of size 0, T(0) = O(1) is returned.

The running time of the estimation method can be expressed recursively as:

T(n)=T(n-1)+T(0)+O(n)=T(n-1)+O(n).

It can be proved that T(n)=O(n^2).

Therefore, if the partitioning is extremely asymmetric at each level of recursion in the algorithm, the running time of the algorithm is O(n^2).

That is, the worst case of the quick sort algorithm is not better than that of insertion sort.

Furthermore, once the array is completely sorted, quick sort runs in O(n^2) time.

In the same situation, the running time of insertion sort is O(n).

//Note, please understand this sentence. When we say the time complexity of a sort, it is only for one element.

//It means that inserting an element into sort, that is, inserting it into an ordered sequence, takes n time.

Let's prove that in the fastest case, that is, in the most balanced partition possible by PARTITION, each subproblem obtained cannot be greater 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).

Intuitively, quick sort is a recursive tree, where PARTITION always produces a 9:1 partition.

The total running time is O(nlgn). The size of the subproblem is shown at each node. The cost of each layer is shown on the right.

Each layer contains a constant c.

=============================================

Please think about the following version by yourself. Which version of the above does it correspond to?

 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

I often wonder why some people clearly understand an algorithm at the time,

After a while, it is completely unfamiliar with the algorithm and does not understand the sequence?

I think, at its core, I still don't fully understand the principle and context of this quick sort algorithm...

As for how to improve the series, we can only find the original author who invented the algorithm and dig out more useful things from him.

=========================================

***, here is another concise example of the quick sort algorithm:

Quicksort Function

 void quicksort( int l, int u)
 { int i, m;
 if (l >= u) return ;
 swap(l, randint(l, u));
 m = l;
 for (i = l+1; i <= u; i++)
 if (x[i] < x[l])
 swap(++m, i);
 swap(l, m);
 quicksort(l, m-1);
 quicksort(m+1, u);
 }

If the function is called in the form of quicksort(0, n-1), then this code will sort a global array x[n].

The two parameters of the function are the subscripts of the subarray to be sorted: l is the lower subscript and u is the higher subscript.

The function call swap(i,j) will swap the two elements x[i] and x[j].

The first swap operation will randomly select a partition element between l and u in a uniformly distributed manner.

Author:July