MHB This is the algorithm of Quicksort

[evinda]

Hi! (Nerd)

This is the algorithm of [m] Quicksort [/m], according to my notes:

Quicksort(A,p,r)
   if (p>=r) return;
   q=Partition(A,p,r);
   swap(A[q],A[r]);
   Quicksort(A,p,q-1);
   Quicksort(A,q+1,r)

Partition(A,p,r)
  x=A[r];
  i=p-1;
  for (j=p; j<r; j++){
       if (A[j]<=x){
          i=i+1;
          swap(A[i],A[j]);
       }
  }
  swap(A[i+1],A[r]);
  return i+1;

Why is this command: [m] swap(A[q],A[r]); [/m] needed at the algorithm of [m]Quicksort[/m]?
Don't we swap these values in [m] Partition [/m] ? (Thinking)

 

[evinda]

Also, which is the cost when $q=p+1$ and which when $q=\lfloor \frac{p+r}{2} \rfloor$ ?

When $q=p+1$, we will have the cost of [m]Partition[/m] that is $O(n)$ and we will have to call the functions [m]Quicksort(A,p,p)[/m] and [m]Quicksort(A,p+,r)[/m], right? How can we find then the cost? (Thinking)Could you also explain me why this: $T(n)=\max_{0 \leq q \leq n-1} (T(q)+T(n-q-1))+\Theta(n)$ is the cost of the worst case? (Worried)