91影视

Fast sorting Algorithm:

鈥� Using a divide-and-conquer strategy, Quick Sort sorts the specified array of items.

鈥� Rapid sort randomly chooses a pivot element v. The specified input array is then separated into three sub-arrays: AL, AR, and Av. Where AL represents the sub-array of items lower than v, AR represents the subarray of elements bigger than v, and Av represents the sub-array of elements equal to v.

鈥� After that, Quick sort recursively sorts the two sub-arrays AL,AR.,

(a)

Pseudocode for sorting quickly:

selection sort is a quicksort function (A[1 ...n])

A[1...] is an array of items .n]

A sorted array A [1...] is the output .n]

v= A[k] chose k at random from 1,2,...,n

AL,AR,Av=split AL,AR,Av= (A[1 ...n],v)

quicksort(AL)

quicksort(AR),

(b)

鈥� In the worst-case scenario, rapid sort chooses the biggest member of the array A every time. That is, AR is an empty sub array every time. AL also has a maximum size of n-1.

鈥� As a result, the problem is simply reduced to a subproblem of size n-1 each time.

In the worst-case scenario, the quicksort algorithm will take the following amount of time to run:

T(n) = T(n-1) + O(n)

Expand the above recurrence

T(n) = T(n-2) +n-1+n

= T(n-3) + n -2 + n 鈥� 1 + n

T(n) = 1+2+3+ .....+n-1+n

=$\frac{n\left(n+1\right)}{2}$

Therefore ,

T(n) = $\frac{n\left(n+1\right)}{2}$ 鈮� c.n² = O(n²) for some constant c > 0

T(n) = $\frac{n\left(n+1\right)}{2}$ 鈮� c.n² = 惟(n²) for some constant c > 0

Therefore, initial definition of bigT(n) = $\frac{n\left(n+1\right)}{2}$ = 惟(n²)

Therefore, the useless condition of running time of the quicksort on an array of size nisO(n²).

(c)

鈥� Assume that pj is the probability that A[k] is the jth biggest element. 1 鈮� j 鈮� n

鈥� pj=1/n so that any component inside the array A could be the jth biggest.

鈥� Also, when the pivot element A[k] is the jth biggest element, suppose Tj is the estimated running time.

鈥� Then total assumption running time, $T\left(n\right)=\underset{j=1}{\overset{n}{鈭�}}{p}_j{T}_j$

鈥� When the pivot element A[k] is the j^th largest, then A_Lhas at most n-j+1 and A_Rhas at most

鈥� j-1 elements.

鈥� ThusT_j is at most T(n-j+1) + T(i-1) +O(n) .

$$\begin{gathered} T\left(n\right)=\underset{j=1}{\overset{n}{鈭�}}{p}_j{T}_j \\ 鈮�\underset{j=1}{\overset{n}{鈭�}}\left(T\left(n-j+1\right)+T\left(j-1\right)+O\left(n\right)\right) \\ 鈮�\frac{1}{2}\underset{j=1}{\overset{n}{鈭�}}\left(T\left(n-j+1\right)+T\left(j-1\right)+O\left(n\right)\right) \\ 鈮�\frac{1}{2}\underset{j=1}{\overset{n}{鈭�}}O\left(n\right)+\frac{1}{2}\underset{j=1}{\overset{n}{鈭�}}T\left(n-j+1\right)+T\left(j-1\right) \\ 鈮�O\left(n\right)+\frac{1}{2}\underset{j=1}{\overset{n}{鈭�}}T\left(n-i\right)+T\left(i\right) \\ 鈮�cn+\frac{1}{2}\underset{j=1}{\overset{n}{鈭�}}T\left(n-i\right)+T\left(i\right) \end{gathered}$$

Hence $T\left(n\right)鈮�O\left(n\right)+\frac{1}{n}\underset{j=0}{\overset{n-1}{鈭�}}T\left(n-i\right)+T\left(i\right)$ ------(1)

To show that T(n) = O(n log n), use induction.

Assume T(n) = O(n log n) implies T(n) 鈮� bn log n ------(2)

Re write equation(1) as follows:

$T\left(n\right)鈮�cn+\frac{2}{n}\underset{j=0}{\overset{n/2}{鈭�}}T\left(n-i\right)+T\left(i\right)$

From inductive hypothesis(equation(2)),

$$\begin{gathered} T\left(n\right)鈮�cn+\frac{2b}{n}\left[\underset{j=0}{\overset{n/2}{鈭�}}\left(n-i\right)\log \left(n-i\right)+i\log i+\underset{j=0}{\overset{n/2}{鈭�}}\left(n-i\right)\log \left(n-i\right)+i\log i\right] \\ T\left(n\right)鈮�cn+\frac{2b}{n}[\underset{j=0}{\overset{n/2}{鈭�}}\left(n-i\right)\log \left(n-i\right)+i\log i \end{gathered}$$

Again, re write above in equation as follows:

$T\left(n\right)鈮�cn+\frac{2b}{n}[\underset{j=1}{\overset{n/4}{鈭�}}\left(n-i\right)\log \left(n-i\right)+i\log i+\underset{j=0}{\overset{n/2}{鈭�}}\left(n-i\right)\log \left(n-i\right)+i\log i]$

Therefore, by induction, it is proved that the solution has run time of $O\left(n\log n\right)$.