https://uadoc.uacdn.net/doubts/PJN79EDBRM/1635483736R97RXMWR.JPEG

DIVIDE AND CONQUER
Consider the PARTITION procedure of quick sort
algorithm.
PARTITION (A, p, r)
1. x = A[r]
2. i = p - 1
3. for j = p to r - 1
4. if A[i] sx
5.
i = i + 1
6.
exchange A[i] with A[j]
7. exchange A[i+1] with A[r]
8. return i + 1
Statement-1 and Statement-2 about PARTITION
procedure.
Statement-1: If all elements in the array have the
same value, PARTITION returns 'r'.
Statement-2: If we modify line 4 of the algorithm to
say this:
=
If A[j] <x and j(mod 2) = (p + 1) (mod
2)
This causes the algorithm to treat half of the
instances of the same value to count as less than,
and the other half to count as greater than, when
all elements have the same value.
Which of the above given statements are TRUE?


English

Educator solution

CS & IT

GATE - CSIT, DSAI & Interview Preparation

GATE, ESE and IIT-JAM

Ace the toughest competitive and government exams in India 

Doubt solution

Doubt details

CS & IT

AUTO-GENERATED

Solutions available

Educator solution