- #1

evinda

Gold Member

MHB

- 3,836

- 0

The following pseudocodes are given.

Code:

```
quicksort(A,p,r)
if p<r then
q<-partition(A,p,r)
quicksort(A,p,q-1)
quicksort(A,q+1,r)
```

Code:

```
partition(A,p,r){
x<-A[r]
i<-p-1
for j<-p to r-1
if A[j]<=x then
i<-i+1
swap(A[i],A[j])
swap(A[i+1],A[r])
return i+1
```

Which value [m]q[/m] does partition return when all the elements of the array have the same value?

Which is the execution time of [m]quicksort[/m] if all the elements of the array [m]A[/m] have the same value?Show that if [m]A[/m] contains different elements and is sorted in decreasing order, the execution time of [m]quicksort[/m] is $\Theta(n^2)$.Show that the best case running time of [m]quicksort[/m] at an array with pairwise different elements is $O(n \lg n)$ .

I thought that the value that the function [m]partition[/m] returns when all the elements of the array have the same value is equal to $q=n$.In this case $q-1-p+1=q-p=n-p$ and $r-q-1+1=r-q=r-n$, right?So $T(n)=T(n-p)+T(r-n)+\Theta(n)$.Can we suppose that $p=1$ and $r=n$?