Question

In our median-finding algorithm (Section 2.4), a basic primitive is the split operation, which takes as input an array S and a value V and then divides S into three sets: the elements less than V , the elements equal to V , and the elements greater than V . Show how to implement this split operation in place, that is, without allocating new memory.

Short answer

The split will be done in place and with time bound:$o\left(n\right)$

Step-by-step solution

Algorithm

Algorithms to performing "split" operations without any need for additional memory:

function $split\left(a\left[1,...,n\right],v\right)$

$$\begin{gathered} hira=1 \\ fori=1ton: \\ ifa\left(i\right)<v: \\ swapa\left[i\right]anda\left[hira\right] \\ hira=hira+1 \\ fori=hiraton: \\ ifa\left(i\right)v: \\ swapa\left[i\right]anda\left[hira\right] \\ hira=hira+1 \end{gathered}$$

Explanation of Algorithm

• “split ” is the function which accepts the array “$s\left[1,...,n\right]$” and a value “” as the input parameters.

• Initially, the variable “ count” is assigned with the value.

• The function has 2 “for ” loops. In the first “ for” loop,

o Process all the elements in the array and brings the elements that are smaller than the value 2 “ ” to front of the array by swapping.

o Thus, the array is split into sub-array by moving all the smaller elements in the array to front.

• It first checks if the value in the k“th” element of the array is less than the value of “ val”.

• If it is true, it swaps the k“th” element of the array “ s” with the position of the array element which has the value of count.

• Then, the value of the “count” is incremented.

• In the second “for” loop,

o Find the position of the value “ val” and move it next to the sub-array by swapping.

• It first checks if the value in the k“th” element of the array is equal to the value of “val ”.

• If it is true, it swaps the k“th” element of the array “ s” with the position of the array element which has the value of count.

• Then, the value of the “ count” is incremented.

o Here, both the “ for” loops require constant time.

Therefore, it takes the running time of $o\left(n\right)$.