Is the following recognition of why pivot in quick sort is considered the best median?
If you have an array similar to the one below, assume that you can select a median for pivot and divide it evenly as shown below.Next, when the same processing is repeated in the group A, the elements of B can be ignored and compared only with the elements in A.Because the element of B is ignored, the number of times of comparison and the number of times of exchange are greatly reduced.Same for B
Thus, if it can be split by median, it can be processed faster.
[4,3,2,5,7,6,9,10,8]
↓ Set the reference value to 6
[4,3,2,5] [Confirm: 6] [7,8,9,10] /// [4,3,2,5] as Group A, [7,8,9,10] as Group B
Processed separately from now on
On the other hand, if the minimum or maximum value is selected as pivot, the group cannot be divided into median values as shown in the example above, resulting in a large bias in the group.In the case of group C, the number of times of comparison and exchange is not reduced much by division.
In other words, the process is slow.
[4,3,2,5,7,6,9,10,8]
↓ Set the reference value to 2
[Confirmation: 2] [4,3,5,6,7,8,9,10] /// [4,3,5,6,7,8,9,10] as group C
↓
Continue to select the minimum value from now on
As a qualitative interpretation, it should be correct because "the number of split times decreases and the overall time calculation decreases." However, it is necessary to calculate the calculation amount properly in order to confirm quantitatively.Try calculating it in the same way as a normal calculation analysis. https://en.wikipedia.org/wiki/Quicksort#Formal_analysis is a good reference.
Below are the details.
© 2024 OneMinuteCode. All rights reserved.