how many swap quicksort take to sort data in avg case?

Question

I am confuse between two answers of stakoverflow,

my question is how many swap quicksort take to sort data in avg case ?

Here is some link saying (1/3)nln(n) swaps on average

link 1(in 1st answer -"Analyse abstract basic operations")

ref link 2 (page no-20 in slide)

other link suggest 1*n*ln(n) swaps on average

link 1

ref link 2 (in last-"And as summary")

I want to know which one is correct ?

Answer 1

The derivation from your last link says:

We assume that average number of swaps during one iteration is 1/2∙(n-1). It means that in average one half of elements is swapped only.

First, it seems that what they call the number of swaps is the number of writes rather than exchanges. So, given their assumption, the total number of exchanges should be (1/2)∙n∙ln(n). Second, I don't think the assumption is correct (it would have been if the pivot had always been the median rather than randomly chosen).

Assume the array {x₁, x₂, ..., x_n} is a random permutation of {1, 2, ..., n}, and z is a randomly chosen pivot. The number of exchanges during the first iteration of the quicksort algorithm is the number of indices i from {1, ..., n} such that i<=z and x_i>z. So the expected value of that number is:

∑_k=1...n(P(z=k)∙∑_{1≤ i ≤ k}(P(x₁>k)))
= (1/n)∙∑_k=1...n(∑_{1≤ i ≤ k}((n-k)/n))
= (1/n)∙∑_k=1...n(k∙(n-k)/n)
= (1/6)(n-1)(n+1)/n
≈ n/6

And since the average number of iterations is 2∙ln(n), the total number of exchanges is (1/3)∙n∙ln(n).