14,976,129 members
1.80/5 (2 votes)
See more:
Time Complexity of this code ?? and how can i optimize it further?
Java
```import java.util.* ;

class GFG
{

static void AlternateRearrange(int arr[], int n)
{
// Sort the array

// Collection.sort() sorts the
// collection in ascending order
Arrays.sort(arr) ;

ArrayList v1 = new ArrayList(); // to insert even values
ArrayList v2 = new ArrayList(); // to insert odd values

for (int i = 0; i < n; i++)
if (arr[i] % 2 == 0)
v1.add(arr[i]);
else
v2.add(arr[i]);

int index = 0, i = 0, j = 0;

boolean flag = false;

// Set flag to true if first element is even
if (arr[0] % 2 == 0)
flag = true;

// Start rearranging array
while (index < n)
{

// If first element is even
if (flag == true)
{
arr[index] = v1.get(i);
i += 1 ;
index += 1 ;
flag = !flag;
}

// Else, first element is Odd
else
{
arr[index] = v2.get(j) ;
j += 1 ;
index += 1 ;
flag = !flag;
}
}

// Print the rearranged array
for (i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}

// Driver code
public static void main(String []args)
{
int arr[] = { 9, 8, 13, 2, 19, 14 };
int n = arr.length ;

AlternateRearrange(arr, n);
}
}```

What I have tried:

This is the best approach i can think of
Posted
Updated 12-Apr-21 19:58pm
v2
Comments
CPallini 12-Apr-21 16:17pm

You didn't tell us what your code is supposed to do.
Samanvay Shrivastava 12-Apr-21 16:20pm

To Rearrange Odd and Even values in Alternate Fashion in Ascending Order from the given array.
raddevus 12-Apr-21 16:27pm

Time-complexity would be O(n^2) because you iterate through n items once in the foreach loop and then once in the while loop.
The print part isn't really a part of the algorithm and should actually be removed into a separate function and shouldn't really be counted as an iteration through the items, since it is just for output.
Patrice T 12-Apr-21 18:09pm

What is your problem with time complexity ?

## Solution 2

Time complexity is probably dominated by the `Array.sort` call, that, according to this page Time Comparison of Arrays.sort(Object[]) and Arrays.sort(int[]) | Baeldung[^] is `O(n log(n))`.
There are still few little improvements you can make to your code in order to make it faster (e.g. first separate odd and even numbers then sort the corresponding arrays, avoid doing additional conditional tests: once you pick the first item then you have to pick items alternatively from the two arrays, without testing each time, ...).

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Top Experts
Last 24hrsThis month
 Richard Deeming 185 OriginalGriff 99 TheRealSteveJudge 90 Wendelius 90 Patrice T 80
 OriginalGriff 4,699 Richard MacCutchan 2,404 Richard Deeming 1,878 Patrice T 990 Dave Kreskowiak 836

CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900