Why Quick Sort Pivot Is Best Median?

Asked 2 years ago, Updated 2 years ago, 39 views

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

algorithm

2022-09-29 22:42

1 Answers

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.

  • "You can ignore the elements of B and compare them only with the elements in A" is a property that can always be done with a quick sort.
  • "Continuing to select the minimum value" seems to be an infinite loop, and it explains the case of the wrong algorithm for quick sorting.


2022-09-29 22:42

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.