Quick sort algoritm


#1

Let P be a quicksort program to sort numbers in ascending order. Let t1 and t2 be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1], respectively. Which of the following holds?

A) t1=t2
B) t1>t2
C) t1<t2
D) t1=t2+5log5

here in set 1 4 element and in set 2 5 element
this will effect on time
correct ans is A or C?


#2

@Mohit_Bawankar i think it should be OPTION A.
We know worst case complexity for quick sort is O(N^2) so i guess here too we will consider that only. I don’t think we will decide it with the value of n because Asymptotically both are O(N^2).


#3

C is answer. Since the array size is mentioned explicitly, t1 will take less time than t2.
if array were of large size, then Time complexity would be O(n^2) that is equal.
In case of ascending or descending array T(n) = T(n-1) + O(n)


#4

C should be the answer as here explicitly time is asked not asymptotic time analysis.


#5

the answer is c because the array 1 is already sorted that means it is in its best case ie. Ω(4 log(4))
and for array 2 it has a avg time of Θ(5 log(5))
and we all know that
Ω(4 log(4)) < Θ(5 log(5))
ie. t1<t2


#6

@Shithanshu_Mishra Quick Sort perfoms worst in case of sorted array with time complexity of O(n^2)
Your explanation is not correct.


#7

t1 = n^2 + constant = 16+c
t2 = n^2 + constant = 25+c
so t1<t2.
option c. because here he asked about the exact time not asymptotic values.


#8

option c is correct.because the time complexicity of quicksort in worst case is O(n^2) and in best and average case is O(nlogn).
so for first array it is already sorted so time complexicity is O(4log4) i.e. t1
for second array it may be the worst case so t2=O(5^2)
clearly t1<t2


#9

Total number of comparisons made by partition algorithm for input array of size n=n+1

(See 2nd page here http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/quicksort.pdf)
[12345] 6
[1] [2345] 5
[2] [345] 4
[3] [45] 3
[4] [5]
Total = 6+5+4+3 = 18

[12345] 6
[123] [45] 4+3
[1] [23] [4][5] 3
[2] [3]

total = 6+4+3+3 = 14
Hence t1>t2


#10

When first element or last element is chosen as pivot, Quick Sort’s worst case occurs for the sorted arrays.

In every step of quick sort, numbers are divided as per the following recurrence.

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