CUET PG 2025 — Computer PYQ

Pivot Selection Ka Antar

• Standard Quicksort: Isme pivot fixed hota hai (pehle se tay).

  $$\text{Pivot}=A[\text{low}]\text{ya}A[\text{high}]$$

• Randomized Quicksort: Isme pivot ko array ke range $[i\dots j]$ mein se randomly uthaya jata hai.

  $$\text{Pivot}=A[\text{random}(i,j)]$$

Iska Impact (Complexity)

Jab hum random pivot chunte hain, toh hum Worst Case hone ki probability ko minimize kar dete hain.

• Worst Case (Standard): Agar input pehle se sorted ho, toh complexity $O(n^2)$ ho jati hai:

  $$T(n)=T(n-1)+\Theta (n)$$

• Expected Case (Randomized): Randomization se humein hamesha balanced partition milne ki umeed rehti hai, jisse average time complexity fix ho jati hai:

  $$E[T(n)]=O(n\log n)$$

Summary: Donon procedures ke kaam karne ka tarika (Logic) ek hi hai, lekin "Pivot Element ka chunav" hi wo point hai jahan dono alag ho jate hain.