1

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 ?

Community
  • 1
  • 1
asd
  • 215
  • 3
  • 9

1 Answers1

2

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 {x1, x2, ..., xn} 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 xi>z. So the expected value of that number is:

∑k=1...n(P(z=k)∙∑1&leq; i &leq; k(P(x1>k)))
= (1/n)∙∑k=1...n(∑1&leq; i &leq; 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).

AbcAeffchen
  • 14,400
  • 15
  • 47
  • 66
Anton
  • 3,113
  • 14
  • 12
  • Doesn't this neglect that (1) not only elements have to move from before to after the pivot, but also from after to before the pivot and (2) some elements that need to move left and some that need to move right of the pivot are done at the same time, while others are not? Moreover, why is P(z=k) = 1/n uniform? – Herbert Jul 23 '18 at 11:13
  • @Herbert (1) Every modification of the array done by Quicksort is an exchange of two elements. What is counted here is the number of exchanges, not the number of write operations (which would be twice as large). (2) Assuming [Hoare partition scheme](https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme), every leftward movement is accompanied with a rightward movement and vice versa. (3) Unfortunately, the last link from the OP is not accessible anymore, but P(z=k) = 1/n by construction. A random subarray element is chosen as the pivot. – Anton Jul 29 '18 at 19:35