Question

The quick sort algorithm always divides the list into two equal sized sublists, then sorts each sublists, and then combines both sublists.. True of False

Answer 1

• Below is the detailed explanation of the problem based on quick sort mentioned above.
• Correct answer is False
• Explanation:

In quick sort algorithm our main aim is to partition the given list around a pivot(which can be selected in different ways consider the first element as pivot for simplicity) and then place the pivot at it's correct position in sorted list and the elements in left side of pivot are smaller than it and on the right side are greater than it.And finally call quicksort for let and right part.

So basically what we do in quick sort is that we try to position the pivot and then call for left and right part hence we get the sorted list.

In quick sort algorithm, list is not always partitioned into two equal sized sublist as consider the case when list is sorted initially and we are applying quick sort algorithm to it by taking the pivot element as the first element, In worst case quick sort will call for two subproblems one for size 0 and the other for size n-1, so the recurrence relation becomes T(n)=T(n-1) + T(0) + O(n)(this extra work for partitioning), so this kind of case results in O(n²) complexity of algorithm.

Normally if list is partitioned into two equal sized lists then recurrence is T(n)=T(n/2) + T(n/2) + O(n) which results in complexity of O(nlogn).

• Algorithm(taking first element as pivot):

#function which sorts a list A with l as starting index and r as ending index+1
def quickSort(A, l, r):
#base case
#if there are at most one element in the list
if r-l<=1:
return()
#considering A[l] as pivot element , do the partitioning
pointer1=l+1
for pointer2 in range(l+1,r):
if A[pointer2] <= A[l]:
(A[pointer1], A[pointer2])=(A[pointer2], A[pointer1])
pointer1=pointer1+1

#now after partitioning move the pivot into its place
(A[l], A[pointer1-1])=(A[pointer1-1], A[l])
#and call recursively for both the parts
quickSort(A,l,pointer1-1)
quickSort(A,pointer1,r)

• So we can see now that in quick sort we do not divide the list into two equal sized sublist then sort each sublist and then combines both sublists. Actually this is known as merge sort algorithm which is also a divide and conquer(similar to quicksort algorithm) algorithm but works differently than quick sort.

So if you still have any doubt regarding this solution please feel free to ask it in the comment section below and if it is helpful then please upvote this solution, THANK YOU.