Given an array of integers A$[1...$ n$],$ we need to push all square num$-$ bers in the array to the front of the array and the non$-$square numbers to the end. Assume that you are given a function ISPERFECTSQUARE$($k$)$ that checks if a given number k is a square number or not in O $(1)$ time.

$($i$)$ DesignaO$($n$2)$time$,$O$(1)$extraspacealgorithmGROUPING$-$NAIVE$($A$[1...$n$])$to solve the problem.

$($ii$)$ Design a $\backslash$Theta $($n$)$ time, O $($n$)$ extra space algorithm GROUPING$-$BETTER$($A$[1...$ n$])$ to solve the problem.