Analysis of Quicksort Algorithm

no_mkd

1. Advantages of Quicksort Algorithm, Why is it Called Quicksort?

Quicksort is an optimization of the merge sort algorithm, inheriting the advantages of merge sort, and also applies the divide-and-conquer idea.

The so-called divide-and-conquer idea is to "divide and rule" a problem, using divide-and-conquer to solve problems requires two steps:

1. How to "divide"? (How to reduce the scale of the problem)
2. How to "conquer"? (How to solve sub-problems)

The predecessor of quicksort is merge sort, and it is precisely because merge sort has shortcomings that cannot be ignored that quicksort was produced. The biggest problem with merge sort is the need for additional storage space, and because the merging process is uncertain, the final position of each element in the sequence is unpredictable. In response to this, quicksort proposes a new idea: spend more time on "divide", and spend less time on "conquer". This solves the problem of additional storage space and improves algorithm efficiency.

The reason why quicksort is called "quick" sort is because it is said to be the fastest in terms of average time, the main reason is hardware-related, each pass of quicksort needs to specify a "pivot" (that is, the value used as the dividing point), all comparisons involved in a pass are compared with this "pivot", then we can put this "pivot" in a register, so efficiency is naturally greatly improved. In addition, the high efficiency of quicksort is also inseparable from the divide-and-conquer idea.

2. Algorithm Idea

According to the idea of quicksort, sorting a known sequence has the following steps:

1. Specify "pivot"

   Note, it is "specify", there is no clear constraint condition, that is to say this pivot is any element, generally we choose two types of pivots: the first element of the current sequence, or randomly select

   Each method has its advantages and disadvantages, the former wins in simplicity, but may affect algorithm efficiency

   In quicksort, the closer the final position of the pivot is to the middle position, the higher the efficiency, may sound a bit strange, note that the pivot is a value (specific element), not the literal meaning of position, when the position of the pivot in the final sequence is too front or too back the algorithm efficiency is not high (similar to "worst case")

   Therefore, the latter reduces the number of worst cases to a certain extent, but random selection requires extra time

   So in specific applications, the first method is generally used to specify the "pivot", that is, directly use the first element of the current sequence as the "pivot"

2. Perform one pass of quicksort

   In quicksort, the ultimate goal of one pass operation is to put the "pivot" where it should go, for example, given sequence {7, -1, 5, 23, 100, 101}, then the result of the first pass of quicksort is {_, _, 7, _, _, _}

   You can see, the first element (pivot) has gone where it should go (in the final result sequence, 7 is in the middle position, right)

3. Perform quicksort on subsequences

   Step 2 not only determines the final position of 7, but also naturally divides the original sequence into two subsequences {_, _} and {_, _, _}, here "_" is used instead of specific values, because we also don't know what the specific result of step 2 is, unless we truly perform one pass of quicksort, of course, it's not necessary here, there will be detailed explanation for specific examples below

   We naturally think of performing the same operation on subsequences, then performing the same operation on subsequences of subsequences... recursion

   When all subsequence lengths are 1, sorting ends

3. Specific Example

Now there is a sequence {9, 0, 8, 10, -5, 2, 13, 7}, we use quicksort algorithm to sort it

First, declare some special notations for easy description

• The capital letter after a number represents a pointer, for example 2.5P means pointer P points to the position where element 2.5 is located
• @ represents garbage numbers, that is to say, it doesn't matter what the current position is, no need to worry about it, there will be specific explanation below
• _ means the element at this position is the same as the previous line (_ means unchanged)

P.S. If you want to truly understand, now take out paper and pen, just relying on eyes is definitely not enough

Now officially begin the analysis of one pass of quicksort process

Explanation:

1. First line is initial state, quicksort needs two pointers L and H (representing low position Low, high position High), one temporary variable temp

   Initially, low pointer L points to first element 9, high pointer H points to last element 7, temp=first element 9 (temp is the so-called "pivot")

2. Perform following operation: (don't ask why first)

   Compare *H with temp, if *H is larger, then move H forward to continue comparison, if *H is smaller, then *L = *H, *H = @ (value H points to becomes garbage number), move L backward

   Because 7 < 9, so change 9 that L points to to 7, change 7 that H points to to garbage number, move L pointer backward, get result of second line

3. Perform following operation: (don't ask why first)

   Compare *L with temp, if *L is smaller, then move L backward to continue comparison, if *L is larger, then *H = *L, *L = @ (value L points to becomes garbage number), move H forward

   Because 0 < 9, so move L backward, get result of third line

4. Because 8 < 9, same as above
5. Because 10 > 9, so change garbage number @ that H points to to 10, change 10 that L points to to garbage number, move H pointer forward, get result of 5th line
6. Because 13 > 9, so move H pointer forward, get result of 6th line
7. Because 2 < 9, so change garbage number @ that L points to to 2, change 2 that H points to to garbage number, and move L pointer backward, get result of 7th line
8. Because -5 < 9, so move L pointer backward to get result of 8th line
9. Perform following operation: (don't ask why first)

   If L = H, then *L = *H = temp, one pass of quicksort ends

   Because L pointer and H pointer coincide, so change garbage number @ that L points to to value of temp 9, one pass ends

   At this point, we have determined the final position of pivot 9, given sequence is also naturally divided into two subsequences {7, 0, 8, 2, -5} and {13, 10}, perform same operation on subsequences, finally can get ordered sequence

Now explain the three groups of operations mentioned above

Simply put, the three groups of operations above are to find the final position of temp, each step ensures that everything before L is smaller than temp, everything after H is larger than temp. Therefore, the element at the position where H and L coincide can only be the value of temp

The three groups of operations mentioned above can be simplified into the following rules, for easy memory:

1. If value L points to is small then L moves, otherwise assign and move pointer
2. If value H points to is large then H moves, otherwise same as above
3. If HL coincide, then assign temp
4. H, L take turns comparing with temp, rule is after one assignment counts as one round end (so initially can also start comparing L with temp, next round H compares with temp, then next round...)

P.S. As for how to move, naturally low position pointer can only move to high position, vice versa. As for which pointer to move after assignment, of course it's the other pointer (not current pointer)

4. Summary

Application of sorting algorithms needs to be considered in combination with specific environment, for example if given sequence is partially ordered, naturally binary insertion algorithm is fastest...

Quicksort is also not the best, its "quick" is built on the basis of comprehensive consideration, specific situations may not be certain

Quicksort is also not omnipotent, for example when given sequence scale is very small, selection sort is much better than quicksort

In addition, common sorting algorithms include:

1. Bucket Sort (Bucketsort)
2. Radix Sort (Radixsort)
3. Insertion Sort (Insertsort)
4. Selection Sort (Selectsort)
5. Merge Sort (Mergesort)
6. Quick Sort (Quicksort)
7. Heap Sort (Heapsort)