GATE DS&AI 2024 | Question: 20

Question

Consider sorting the following array of integers in ascending order using an inplace Quicksort algorithm that uses the last element as the pivot.
\begin{array}{|l|l|l|l|l|}
\hline 60 & 70 & 80 & 90 & 100 \\
\hline
\end{array}

The minimum number of swaps performed during this Quicksort is $\_\_\_\_\_\_\_\_$.

Comments

@raghu_46

how ?

 

---

no of comp needed 10
cuz last element choosen as pivot then comp with n-1 element so 4+3+2+1 its become 10 :)

---

What about self swaps ?I considered those too ...

Answer 1

To determine the minimum number of swaps performed during the Quicksort algorithm, we first need to partition the array using the last element (100) as the pivot. Then, we move all elements smaller than the pivot to the left of it and all elements greater than the pivot to the right of it.

Given the array:

\[ \text{[60, 70, 80, 90, 100]} \]

Using the last element (100) as the pivot, after partitioning, the array may look like this:

\[ \text{[60, 70, 80, 90, 100]} \]

Since the pivot element (100) is already at its correct position in the sorted array, there are no swaps needed for this partitioning step.

Next, we recursively apply the same process to the left and right subarrays. For the left subarray \([60, 70, 80, 90]\), the pivot is 90, and after partitioning, the array may remain the same as the pivot is already at its correct position.

For the right subarray, there is only one element (100), which is already sorted.

Therefore, no swaps are needed in this case.
So, the minimum number of swaps performed during this Quicksort is 0.

Comments

@pavansan Yes
as we know that partition algo just put one elment (pivot) into correct position everytime it runs, swap occurs at the last of partition algo to send pivot to the correct position, BUT here pivot is already at correct position 

also swap happens between non-pivot elements but that won't happen as well because every element is at it's correct position

---

then why the time complexity is o(n^2) if the there is no swap in sorted array(i'm not able to process) someone please help :)

---

because of there is n-1 comparison at first partition, n-2 comparison at 2nd partition so on...   n + (n-1) + (n-2) + (n-3) + ....1

Time compexity is O(n^2)

Answer 2

0

As array elements are already sorted so in quicksort partitioning there is no any swap required

(taking first or last element as pivot doesn't matter)

Comments

@arpit.jha bt question is asking minimum and in cormen its hoare's implementation given then i think we should follow that only

---

@arpit.jha,

Given that inplace quicksort algorithm - which is not a standard one. That means, optimizations can be done.

Therefore we can optimizate the quick sort in way that the extra swaps can be avoided with introducing some comparissions.

As minimum asked with the sorted areay - zero is the best choice.

---

@Shaik Masthan got it word "minimum" binds us to take an implementation that gives less swaps

Answer 3

Concept QuickSort :

Array: Sorted.

Pivot choice: Last element. Largest Element.

Then :
Sorted + Last element pivot = Largest element is pivot.
All elements left are smaller. No swaps needed.

 

Answer 4

✅ Total Comparisons:

4+3+2+1=10

✅ Total Swaps (Minimum):

Since array is already sorted and pivot is always largest → no swaps needed

Answer 5

 

Answer 6

Array already  ascending order me hai to no swaps
 only comparison required
 

Comments

thanks brooo