Like mergeSort, quickSort is a sorting algorithm based on the divide-and-conquer

Question

Like mergeSort, quickSort is a sorting algorithm based on the divide-and-conquer paradigm. As we have seen, the worst case running time of mergeSort is Theta(n log n), as was shown by solving the mergeSort recurrence relation. The situation with the running time of quickSort is a bit murkier, and more interesting. Here is Python code for quickSort that I wrote a few years ago: def partition, (L, first, last): # Pick L[first] as the "pivot" around which we partition the list p = first for current in range (p + 1, last + 1): if L[current]

Explanation / Answer

Let array be

4 3 2 1

Step1:

Partion of ( array , 0, 3)

P = 0

Current goes from 1 to 3

When current=1

L[current] = l [ 1 ] = 3

L[p]= l[ 0] = 4

L [ Current ] < L [ P ] swap L [ Current] , L[p]

Step:2

Array 3 4 2 1 now p=p+1 ; p=1,current=2

L[current] = l [2] =2

L[ p ]= l[1] = 4

L[currnet] < l[p] so swap

Array 3 2 4 1 p = p+1 so p=2 current =3

Step :3

L[current] = l [3] =1

L[p]= l[2] =4

  L[currnet] < l[p] so swap

Array 3 2 1 4 and p= p+1 so p=3

Pivot is 3

There are 4 elements we take 3 steps to find pivot

So to find pivot of n elements it takes n-1 in worst case

So partion() time complexity is O ( n )

So genenratequicksort( ) will be

So T(N) = T(N-1) + cN, N > 1

T(N-1) = T(N-2) + c(N-1)

T(N-2) = T(N-3) + c(N-2)

T(N-3) = T(N-4) + c(N-3)

T(2) = T(1) + c.2

T(N) + T(N-1) + T(N-2) + … + T(2) =

= T(N-1) + T(N-2) + … + T(2) + T(1) + c(N) + c(N-1) + c(N-2) + … + c.2

T(N) = T(1) + c(2 + 3 + … + N)

T(N) = 1 + c(N(N+1)/2 -1)

Therefore T(N) = O(N2)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.