Consider the
given array having unsorted elements, and answer the two questions asked
below.
Question no 01: (10: Marks)
Apply quick sort
algorithm on below given array by taking value (30) as pivot element and write
down the resulted arrays till first pass only.
|
30
|
48
|
10
|
20
|
70
|
15
|
80
|
40
|
∞
|
Answer:
Pivot = 30
P=0, q = 0, s = 1
|
30
|
48
|
10
|
20
|
70
|
15
|
80
|
40
|
∞
|
P = 0, q = 1, s = 2
|
30
|
10
|
48
|
20
|
70
|
15
|
80
|
40
|
∞
|
P = 0, q = 1, s = 3
|
30
|
10
|
20
|
48
|
70
|
15
|
80
|
40
|
∞
|
P = 0, q = 2, s = 4
|
30
|
10
|
48
|
20
|
70
|
15
|
80
|
40
|
∞
|
P = 0, q = 2, s = 5
|
30
|
10
|
48
|
20
|
15
|
70
|
80
|
40
|
∞
|
P = 0, q = 4, s = 6
|
30
|
10
|
48
|
20
|
15
|
70
|
80
|
40
|
∞
|
P = 0, q = 4, s = 7
|
30
|
10
|
48
|
20
|
70
|
15
|
80
|
40
|
∞
|
P = 0, q = 6, s = 8
|
30
|
10
|
48
|
20
|
70
|
15
|
40
|
80
|
∞
|
P = 0, q = 6, s = 8
|
30
|
10
|
48
|
20
|
70
|
15
|
40
|
80
|
∞
|
Question no 02: (10: Marks)
Write down the
recurrence relation of quick sort in case of average or normal case means when
the pivot’s element location is the middle of array.
Solution:
T(1) = c if n =
1 eq 1
T(n) =
T(n/2)+T(n/2) + cn if n>1 eq 2
T(n) = 2(T(n/4))+cn 1st
Term 21
T(n) =
2(2(T(n/4))+cn) + 1cn
T(n) = 4T(n/4) +
2cn 2nd Term 22
T(n) =
4(2(T(n/8))+cn) + 2cn
T(n) = 8T(n/8) +
3cn 3rd
– Term 23
T(n) = 23T(n/23)
+ 3cn
For some term k
T(n) = 2kT(n/2k)
+ kn
n = 2k
k = log2 n
T(n) = nT(n/n) +
cnlog2 n
T(n) = nT(1) +
cnlog2 n
T(n) = nc +
cnlog2 n
T(n) = cnlog2
n
T(n) = c(nlog2
n)
O(nlog2 n) Final Answer.
No comments:
Post a Comment