what is meaning n average compared from array with length x in QuickSort

Question

in this formula and continue this question I think if we assume n equal 3 so we have array like A={4,5,7}

and with the formula, we get 8 from n=3 and this means is 8 average compare for array with length 3 and this so weird!

1. what is exactly happening in quickSort to get average compare 8 form array so short! and occurs many compare and that is so bad! is true?

I think if we compare the array with 4 step is so faster than use quickSort!

Answer 1

So your question seems to be about the formula

E[X] = E[sum(i, 1, n-1, sum(j, i+1, n, p_i,j))]

in this image you uploaded in the other question.

Here E[X] means the expected value. In simpler terms: the value X will get on average if you do the experiment (sorting a random array) many many times.

p_i,j is the chance that item i and item j are compared to each other during the run of the algorithm. For a good algorithm, it happens that item i is compared to item k and item k to item j, which often makes it unnecessary to really compare item i and item j. Therefore, the better the algorithm, the lower this probability p_i,j.

In the worst case, for example when n is only 3, you can have p_i,j = 1. If you then calculate the formula, you get that for n=3, E[X]=3 because there are only three combinations for (i,j) : (1,2), (1,3) and (2,3). This means that for n=3 always 3 comparisons are done. This is equal for all good algorithms, because you can not take advantage of item_i < item_k < item_j.

For larger n, there are many chances to take advantage of not needing to explicitly test all item_i versus all item_j. A detailed analysis is for example available in the Khan Academy article.